Ну блин ,... у тебя полное динамика понятное дело .
Во первых ! Для начала ускорение,это избавиться от ненужного вначале ..
то есть если есть (X1,Y1),(X2,Y2) то нам не надо использовать (X1,Y1), если (X2>=X1 && Y2>=Y1) ===>
если есть (5,4) и (6,4) то (5,4) можно удалить спокойно так как на ответ это не влияет,(6,4) поглощает (5,4)
Ну а далее эта динамика только она не бегает по всем 1<=j<=i .. она бегает по заведомо выбранным оптимальным ans(j)...
#include<algorithm>
#include<iostream>
using namespace std;
#define forr(i,x,y) for(int i=(int)(x); i<(int)(y); i++)
#define mem(a,b) memset(a,b,sizeof(a))
#define x first
#define y second
typedef pair<long long,long long> vll;
pair<int,int> a[50010];
vll f[50010];
int N,n=0,l=0,r=1;
long long fc=0,w=0;
bool compare(pair<int,int> a,pair<int,int> b) {
if(a.x<b.x) return true;
if(a.x>b.x) return false;
if(a.y<b.y) return true;
return false;
}
bool lesss(vll a,vll b,vll c) {
return ((a.y-b.y)*(b.x-c.x)<=(b.y-c.y)*(a.x-b.x));
}
int main() {
freopen("acquire.in","r",stdin);
freopen("acquire.out","w",stdout);
scanf("%d",&N);
mem(a,0); mem(f,0);
forr(i,0,N) scanf("%d %d",&a[i].x,&a[i].y);
sort(a,a+N,compare);
forr(i,0,N) { n++;
while(n && a[i].x>=a[n-1].x && a[i].y>=a[n-1].y) n--;
a[n]=a[i];
}
f[(n++)-n]=make_pair(a[0].y,0);
forr(i,0,n) { fc=-1;
forr(j,l,r) {
w=f[j].x*a[i].x+f[j].y;
if(w<fc || fc<0) { fc=w; l=j; } else break;
}
if(i<n-1) {
f[r++]=make_pair(a[i+1].y,fc);
while(r-l>2 && lesss(f[r-3],f[r-2],f[r-1])) { f[r-2]=f[r-1]; r--; }
}
}
cout<<fc;
}
Вот мой CODE