Динамика + Выпуклая Оболочка

http://tjsct.wikidot.com/usaco-mar08-gold

Я алгоритм вроде понял , но непонятно было какое отношение имеет выпуклая оболочка .Теперь все ясно.
Спасибо

Ну блин ,... у тебя полное динамика понятное дело .
Во первых ! Для начала ускорение,это избавиться от ненужного вначале ..
то есть если есть (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

то есть я так понял у тебя найти максимальное в промежутке ???? если да,то блина просто структуру заведи,что бы за О(1) искать минимальное на промежутке .. если не так понял то извини .

Нет,ну во-первых не обязан ты писать за О(Н),можешь и за О(Нлог(Н)),сильно не повлияет.
Во-вторых они это делают так,
пусть ANS(i) это ответы для первых I точек,X(i), Y(i) - размеры блоков.
Тогда что мы делаем на каждом шаге
представляем как бы точки вида - (Y(i),ANS(i))

f[(n++)-n]=make_pair(a[0].y,0);
......make_pair(a[i+1].y,fc)

Вначале это ANS = 0, Y(0)
Далее это будет Y(i), ANS(i)
Теперь на каждый момент I, мы будем иметь границу (L,R) .
На каждом шаге когда мы хотим посчитать ANS(i), мы бегаем только по J = L..R .
Так же мы на каждом шаге двигаем эти (L,R), что бы поддерживать оптимальность.
Их мы двигаем так.
L = максимальному оптимальному J на данный момент I.
R = двигаем вниз пока ответ хуже чем надо.
И того в итоге мы сделаем ~~O(N) шагов ...
Вроде это видно из CODE.