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.

Download