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.

Download