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.