MFISH - Catch Fish
Tác giả: RR
Ngôn ngữ: Pascal
//Written by RR
{$MODE OBJFPC}
uses math;
const
FINP = '';
FOUT = '';
MAXN = 100111;
var
f1,f2 : text;
n,m : longint;
a,b,d : array[0..MAXN] of longint;
f : array[0..1,0..MAXN] of longint;
procedure openF;
begin
assign(f1,FINP); reset(f1);
assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
close(f1);
close(f2);
end;
procedure inp;
var
i:longint;
begin
read(f1,n);
for i:=1 to n do
begin
read(f1,a[i]);
a[i]:=a[i]+a[i-1];
end;
read(f1,m);
for i:=1 to m do
read(f1,b[i],d[i]);
end;
procedure solve;
var
i,now,last,first,ln,save:longint;
begin
b[m+1]:=1000111000;
ln:=0;
for i:=1 to m do
begin
save:=ln; ln:=0;
now:=i and 1;
for last:=max(b[i-1]+d[i],b[i]) to min(min(b[i+1]-1,b[i]+d[i]-1),n) do
begin
first:=last-d[i];
if first<b[i-1]+d[i-1] then
f[now,last]:=max(f[now,last-1],f[1-now,first]+a[last]-a[first])
else f[now,last]:=max(f[now,last-1],save+a[last]-a[first]);
ln:=max(ln,f[now,last]);
end;
end;
writeln(f2,ln);
end;
procedure swap(var a,b:longint); inline;
var
tmp:longint;
begin
tmp:=a; a:=b; b:=tmp;
end;
procedure sort(l,r:longint); inline;
var
i,j,mid:longint;
begin
i:=l; j:=r; mid:=b[l+random(r-l+1)];
repeat
while b[i]<mid do inc(i);
while b[j]>mid do dec(j);
if i<=j then
begin
swap(b[i],b[j]);
swap(d[i],d[j]);
inc(i); dec(j);
end;
until i>j;
if i<r then sort(i,r);
if l<j then sort(l,j);
end;
begin
openF;
inp;
sort(1,m);
solve;
closeF;
end.