Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

const fi='';
      fo='';
      maxn=100010;
var n,m,re:longint;
    a,f,lt,d,pos,b:array[0..maxn] of longint;

procedure rf;
var i,t:longint;
begin
     assign(input,fi);
     reset(input);
     readln(n);
     a[0]:=0;
     for i:=1 to n do
     begin
          read(t);
          a[i]:=a[i-1]+t;
     end;
     readln;
     readln(m);
     fillchar(d,sizeof(d),0);
     for i:=1 to m do
     begin
          readln(t,lt[i]);
          d[t]:=i;
     end;
     close(input);
end;

procedure sort;
var i,j:longint;
begin
     j:=0; pos[0]:=0; b[0]:=0;
     for i:=1 to n do
         if d[i]>0 then
         begin
              inc(j);
              pos[j]:=i; b[j]:=lt[d[i]];
         end;
end;

function max(a,b:longint):longint;
begin
     if a>=b then max:=a else max:=b;
end;

function calc(x,y:longint):longint;
begin
     calc:=a[x]-a[x-y];
end;

procedure pr;
var i,l,ll,r,rr,j:longint;
begin
     fillchar(f,sizeof(f),0);
     sort;
     for i:=1 to m do
     begin
          ll:=pos[i]; l:=pos[i-1]+b[i];
          if l<ll then l:=ll;
          for j:=ll to l-1 do f[j]:=f[j-1];
          if i<m then rr:=pos[i+1]-1
          else rr:=n;
          r:=pos[i]+b[i]-1;
          if r>rr then r:=rr;
          f[l]:=f[l-b[i]]+calc(l,b[i]);
          for j:=l+1 to r do
              if j-b[i]>=b[i-1] then
                 f[j]:=max(f[j-b[i]]+calc(j,b[i]),f[j-1]);
          for j:=r+1 to rr do f[j]:=f[j-1];
     end;
     for j:=l to r do
         if f[j]>re then re:=f[j];
end;

procedure wf;
begin
     assign(output,fo);
     rewrite(output);
     write(re);
     close(output);
end;

begin
     rf;
     pr;
     wf;
end.

Code mẫu của ladpro98

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.

Code mẫu của RR

//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.

Code mẫu của hieult

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;
typedef long double ld;
//typedef double ld;
typedef unsigned int ui;
typedef unsigned long long ull;

#define Rep(i,n) for(__typeof(n) i = 0; i < (n); ++i)
#define Repd(i,n) for(__typeof(n) i = (n)-1; i >= 0; --i)
#define For(i,a,b) for(__typeof(b) i = (a); i <= (b); ++i)
#define Ford(i,a,b) for(__typeof(a) i = (a); i >= (b); --i)
#define Fit(i,v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
#define Fitd(i,v) for(__typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++i)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
#define ms(a,x) memset(a, x, sizeof(a))
#define nl puts("")
#define sp printf(" ")
#define ok puts("ok")
//#include <conio.h>

template<class F, class T> T convert(F a, int p = -1) { stringstream ss; if (p >= 0) ss << fixed << setprecision(p); ss << a; T r; ss >> r; return r; }
template<class T> void db(T a, int p = -1) { if (p >= 0) cout << fixed << setprecision(p); cout << a << " "; }
template<class T> T gcd(T a, T b) { T r; while (b != 0) { r = a % b; a = b; b = r; } return a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T> T sqr(T x) { return x * x; }
template<class T> T cube(T x) { return x * x * x; }
template<class T> struct Triple { T x, y, z; Triple() {} Triple(T _x, T _y, T _z) : x(_x), y(_y), z(_z) {} };
template<class T> Triple<T> euclid(T a, T b) { if (b == 0) return Triple<T>(1, 0, a); Triple<T> r = euclid(b, a % b); return Triple<T>(r.y, r.x - a / b * r.y, r.z); }
template<class T> int getbit(T s, int i) { return (s >> i) & 1; }
template<class T> T onbit(T s, int i) { return s | (T(1) << i); }
template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); }
template<class T> int cntbit(T s) { return s == 0 ? 0 : cntbit(s >> 1) + (s & 1); }
const int bfsz = 1 << 16; char bf[bfsz + 5]; int rsz = 0;int ptr = 0;
char gc() { if (rsz <= 0) { ptr = 0; rsz = fread(bf, 1, bfsz, stdin); if (rsz <= 0) return EOF; } --rsz; return bf[ptr++]; }
void ga(char &c) { c = EOF; while (!isalpha(c)) c = gc(); }
int gs(char s[]) { int l = 0; char c = gc(); while (isspace(c)) c = gc(); while (c != EOF && !isspace(c)) { s[l++] = c; c = gc(); } s[l] = '\0'; return l; }
template<class T> bool gi(T &v) {
    v = 0; char c = gc(); while (c != EOF && c != '-' && !isdigit(c)) c = gc(); if (c == EOF) return false; bool neg = c == '-'; if (neg) c = gc();
    while (isdigit(c)) { v = v * 10 + c - '0'; c = gc(); } if (neg) v = -v; return true;
}

const double PI = 2 * acos(0);
const string months[] = {"January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November", "December"};
const int days[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int dr[] = {-1, +0, +1, +0};
const int dc[] = {+0, +1, +0, -1};
const int inf = (int)1e9 + 5;
const ll linf = (ll)1e16 + 5;
const ld eps = ld(1e-9);
const ll mod = 100000007;
typedef pair<int, int> II;

#define maxn 100005

int n, a[maxn], f[maxn];
int m;
II P[maxn];

int main(){
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    a[0] = 0;
    gi(n); For(i, 1, n) { gi(a[i]); a[i] += a[i - 1];}
    gi(m);
    For(i, 1, m) { gi(P[i].fi); gi(P[i].se);}
    sort(P + 1, P + n + 1);
    f[0] = 0;
    int run = 0;
    P[0].fi = 0; P[0].se = 0;
    For(i, 1, n){
        f[i] = f[i - 1];
        while(run < n && P[run + 1].fi <= i) run++;
        if(run > 0)
            if(P[run].fi + P[run].se - 1 >= i && i - P[run].se >= P[run - 1].fi)
                f[i] = max(f[i], f[i - P[run].se] + a[i] - a[i - P[run].se]);
    }
    cout << f[n];
}

Code mẫu của ll931110

{$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.