MFISH - Catch Fish
Tác giả: ladpro98
Ngôn ngữ: Pascal
program MFISH;
uses math;
const fi='';
maxn=100005;
type e=record
s,l,lim:longint;
end;
var ship:array[0..maxn] of e;
f,a,prev,sum:array[0..maxn] of longint;
chk:array[0..maxn] of boolean;
n,i,j,jj,m,pos,res:longint;
inp:text;
procedure sort(l,r:longint);
var p,i,j:longint;
t:e;
begin
if l>=r then exit;
i:=l;j:=r;
p:=ship[random(r-l+1)+l].lim;
repeat
while ship[i].lim<p do inc(i);
while ship[j].lim>p do dec(j);
if i<=j then begin
if i<j then begin
t:=ship[i];
ship[i]:=ship[j];
ship[j]:=t;
end;
inc(i);dec(j);
end;
until i>j;
sort(l,j);sort(i,r);
end;
begin
assign(inp,fi);reset(inp);
readln(inp,n);
for i:=1 to n do read(inp,a[i]);
for i:=1 to n do sum[i]:=sum[i-1]+a[i];
readln(inp,m);
for i:=1 to m do readln(inp,ship[i].s,ship[i].l);
for i:=1 to m do ship[i].lim:=ship[i].s+ship[i].l-1;
for i:=1 to m do chk[ship[i].s]:=true;
for i:=1 to n do if chk[i-1] then prev[i]:=i-1
else prev[i]:=prev[i-1];
sort(1,m);j:=1;ship[0].l:=1;ship[0].lim:=0;
for i:=1 to n do begin
f[i]:=f[i-1];
while (j<=m) and (ship[j].s<=i) do inc(j);
dec(j);
if ship[j].lim<i then continue;
jj:=j;
while (ship[jj].lim>=i) do begin
pos:=i-ship[jj].l+1;
if prev[ship[jj].s]<pos then
f[i]:=max(f[i],f[pos-1]+sum[i]-sum[pos-1]);
dec(jj);
end;
if j=m then
res:=max(res,f[i]);
end;
write(res);
end.