MFISH - Catch Fish
Tác giả: ll931110
Ngôn ngữ: Pascal
{$MODE DELPHI}
Program MFISH;
Const
input = '';
output = '';
maxn = 100000;
Var
n,m: integer;
a,len,res,sum: array[0..maxn] of integer;
fn,st: array[0..maxn] of integer;
heap: array[1..maxn] of integer;
nHeap: integer;
Procedure init;
Var
f: text;
i: integer;
Begin
Assign(f, input);
Reset(f);
Readln(f, n);
sum[0]:= 0;
For i:= 1 to n do
Begin
read(f, a[i]);
sum[i]:= sum[i - 1] + a[i];
End;
st[0]:= -1;
Readln(f, m);
For i:= 1 to m do
Begin
Readln(f, st[i], len[i]);
fn[i]:= st[i] + len[i] - 1;
If fn[i] > n then fn[i]:= n;
End;
Close(f);
End;
{Procedure swap(var x,y: integer);
Var
t: integer;
Begin
t:= x;
x:= y;
y:= t;
End;
Procedure quicksort;
Procedure partition(l,h: integer);
Var
i,j,p: integer;
Begin
If l >= h then exit;
i:= l;
j:= h;
p:= st[random(h - l + 1) + l];
Repeat
While st[i] < p do inc(i);
While st[j] > p do dec(j);
If i <= j then
Begin
If i < j then
Begin
swap(st[i],st[j]);
swap(fn[i],fn[j]);
swap(len[i],len[j]);
End;
inc(i);
dec(j);
End;
Until i > j;
partition(l,j);
partition(i,h);
End;
Begin
partition(1,m);
End;}
Procedure push(x: integer);
Var
parent,child: integer;
Begin
inc(nHeap);
child:= nHeap;
parent:= child div 2;
While (parent > 0) and (fn[heap[parent]] > fn[x]) do
Begin
heap[child]:= heap[parent];
child:= parent;
parent:= child div 2;
End;
heap[child]:= x;
End;
Procedure pop;
Var
r,c,x: integer;
Begin
x:= heap[nHeap];
dec(nHeap);
r:= 1;
While r * 2 <= nHeap do
Begin
c:= r * 2;
If (c < nHeap) and (fn[heap[c + 1]] < fn[heap[c]]) then inc(c);
If fn[x] <= fn[heap[c]] then break;
heap[r]:= heap[c];
r:= c;
End;
heap[r]:= x;
End;
Procedure solve;
Var
i,j,tmp,n1: integer;
Begin
res[0]:= 0;
nHeap:= 0;
n1:= 1;
For i:= 1 to n do
Begin
res[i]:= res[i - 1];
While (n1 <= m) and (st[n1] = i) do
Begin
push(n1);
inc(n1);
End;
For j:= 1 to nHeap do
Begin
tmp:= i - len[heap[j]];
If (tmp >= 0) and (tmp >= st[heap[j] - 1]) and (res[i] < res[tmp] + sum[i] - sum[tmp])
then res[i]:= res[tmp] + sum[i] - sum[tmp];
End;
While (nHeap > 0) and (fn[heap[1]] = i) do pop;
End;
End;
Procedure printresult;
Var
f: text;
Begin
Assign(f, output);
Rewrite(f);
Writeln(f, res[n]);
Close(f);
End;
Begin
init;
{ quicksort;}
solve;
printresult;
End.