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.

Download