Настройки поиска (Страница 6 из 6)

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

#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; 
}

{$r-,s-,q-,i-,o+}
const mn=200004;
type dataMass = array[-1..mn]of longint;
var a,b,c,ind,indind,aa,bb : dataMass;
 i,st,k,res,resx,resy,cres : longint;
 alcp,blcp : array[1..20]of dataMass;
 ch : char;

procedure sort(n : longint);
 var i : longint;

 procedure radixsort(var a,b : dataMass);
  var i : longint;
  begin
   fillchar(c,sizeof(c),0);
   for i:=1 to n do inc(c[a[i]]);
   for i:=1 to mn do c[i]:=c[i]+c[i-1];
   for i:=1 to n do begin
    inc(c[a[i]-1]);
    aa[c[a[i]-1]]:=a[i];
    bb[c[a[i]-1]]:=b[i];
    indind[c[a[i]-1]]:=ind[i];
   end;
   for i:=1 to n do begin
    a[i]:=aa[i];
    b[i]:=bb[i];
    ind[i]:=indind[i];
   end;
  end;

 begin
  for i:=1 to n do ind[i]:=i;
  radixsort(b,a);
  radixsort(a,b);
 end;

function find(x,y,st,k : longint): longint;
 var res : longint;
 begin
  res:=0;
  repeat
   if y+st*2+ord(st=0)<a[0]+2 then
   if (alcp[k][y]=alcp[k][x]) and (blcp[k][y]=blcp[k][x]) then begin
    inc(res,st*2+ord(st=0));
    inc(x,st*2+ord(st=0));
    inc(y,st*2+ord(st=0));
   end;
   dec(k);
   st:=st shr 1;
  until k=0;
  find:=res;
 end;

begin
 {assign(input,'input.txt');
 reset(input);
 assign(output,'output.txt');
 rewrite(output);}
 fillchar(a,sizeof(a),0);
 fillchar(b,sizeof(b),0);
 fillchar(ind,sizeof(ind),0);
 while not eoln do begin
  read(ch);
  inc(a[0]);
  a[a[0]]:=ord(ch);
  b[a[0]]:=ord(ch);
 end;
 readln;
 inc(a[0]);
 a[a[0]]:=222;
 b[a[0]]:=222;
 b[0]:=a[0]+1;
 while not eoln do begin
  read(ch);
  inc(a[0]);
  a[a[0]]:=ord(ch);
  b[a[0]]:=ord(ch);
 end;
 st:=0;
 k:=0;
 repeat
  inc(k);
  alcp[k]:=a;
  blcp[k]:=b;
  sort(a[0]);
  if st>=a[0] then break;
  st:=st*2+ord(st=0);
  c[ind[1]]:=1;
  for i:=2 to a[0] do c[ind[i]]:=c[ind[i-1]]+ord((a[i]<>a[i-1]) or (b[i]<>b[i-1]));
  for i:=1 to a[0] do begin
   a[i]:=c[i];
   b[i]:=0;
   if i+st<=a[0] then b[i]:=c[i+st];
  end;
 until false;
 res:=0;
 resx:=0;
 resy:=0;
 for i:=2 to a[0] do
 if (ind[i-1]>=b[0]) and (ind[i]<b[0]) then begin
  cres:=find(ind[i],ind[i-1],st,k);
  if cres>res then begin res:=cres; resx:=ind[i]-1; resy:=ind[i-1]-b[0]; end;
 end else
 if (ind[i-1]<b[0]) and (ind[i]>=b[0]) then begin
  cres:=find(ind[i],ind[i-1],st,k);
  if cres>res then begin res:=cres; resx:=ind[i-1]-1; resy:=ind[i]-b[0]; end;
 end;
 write(res,' ',resx,' ',resy);
 {close(input);
 close(output);}
end.