MFISH - Catch Fish

Tác giả: flashmt

Ngôn ngữ: Pascal

const fi='';
      fo='';
      maxn=100010;
var n,m,re:longint;
    a,f,lt,d,pos,b:array[0..maxn] of longint;

procedure rf;
var i,t:longint;
begin
     assign(input,fi);
     reset(input);
     readln(n);
     a[0]:=0;
     for i:=1 to n do
     begin
          read(t);
          a[i]:=a[i-1]+t;
     end;
     readln;
     readln(m);
     fillchar(d,sizeof(d),0);
     for i:=1 to m do
     begin
          readln(t,lt[i]);
          d[t]:=i;
     end;
     close(input);
end;

procedure sort;
var i,j:longint;
begin
     j:=0; pos[0]:=0; b[0]:=0;
     for i:=1 to n do
         if d[i]>0 then
         begin
              inc(j);
              pos[j]:=i; b[j]:=lt[d[i]];
         end;
end;

function max(a,b:longint):longint;
begin
     if a>=b then max:=a else max:=b;
end;

function calc(x,y:longint):longint;
begin
     calc:=a[x]-a[x-y];
end;

procedure pr;
var i,l,ll,r,rr,j:longint;
begin
     fillchar(f,sizeof(f),0);
     sort;
     for i:=1 to m do
     begin
          ll:=pos[i]; l:=pos[i-1]+b[i];
          if l<ll then l:=ll;
          for j:=ll to l-1 do f[j]:=f[j-1];
          if i<m then rr:=pos[i+1]-1
          else rr:=n;
          r:=pos[i]+b[i]-1;
          if r>rr then r:=rr;
          f[l]:=f[l-b[i]]+calc(l,b[i]);
          for j:=l+1 to r do
              if j-b[i]>=b[i-1] then
                 f[j]:=max(f[j-b[i]]+calc(j,b[i]),f[j-1]);
          for j:=r+1 to rr do f[j]:=f[j-1];
     end;
     for j:=l to r do
         if f[j]>re then re:=f[j];
end;

procedure wf;
begin
     assign(output,fo);
     rewrite(output);
     write(re);
     close(output);
end;

begin
     rf;
     pr;
     wf;
end.

Download