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

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

int n, k, cost[111], len[111], pos[111], f[20200];

int main()
{
    cin >> n >> k;
    for (int i = 1; i <= k; i++) cin >> len[i] >> cost[i] >> pos[i];
    for (int i = 1; i < k; i++)
        for (int j = i + 1; j <= k; j++)
            if (pos[i] > pos[j])
            {
                swap(pos[i], pos[j]);
                swap(len[i], len[j]);
                swap(cost[i], cost[j]);
            }

    for (int i = 1; i <= k; i++)
    {
        int best = - (1 << 29), decCost = len[i] * cost[i], incCost = 0;
        for (int j = pos[i] + len[i] - 1; j >= pos[i]; j--)
        {
            if (j >= len[i]) best = max(best, f[j - len[i]] + incCost);
            if (j <= n) f[j] = max(f[j], best + decCost);
            incCost += cost[i];
            decCost -= cost[i];
        }
        for (int j = 1; j <= n; j++) f[j] = max(f[j], f[j - 1]);
    }

    cout << f[n] << endl;
}

Code mẫu của ladpro98

#include <cstdio>
#include <algorithm>
#include <iostream>

struct man {
    int l, p, s;
};
bool cmp(const man& a, const man& b) {
    return a.s < b.s;
}
const int M = 101;
const int N = 16666;
const int oo = 1000000009;
using namespace std;

man a[M];
int F[M][N];
int ma[N];
int n, m;

int main()
{
    int i, j;
    scanf("%d %d", &n, &m);
    for(i=1; i<=m; i++) scanf("%d %d %d", &a[i].l, &a[i].p, &a[i].s);
    sort(a+1, a+1+m, cmp); ma[n + 1] = -a[1].p * (n + 1);
    for(i=1; i<=n; i++) ma[i] = max(ma[i+1], -a[1].p * i);
    for(j=1; j<=m; j++) {
        for(i=1; i<=n; i++) {
            F[j][i] = max(F[j-1][i], F[j][i-1]);
            if (i <= a[j].s + a[j].l - 1 && a[j].s <= i)
                F[j][i] = max(F[j][i], ma[max(0, i - a[j].l)] + a[j].p * i);
        }
        #define S a[j + 1].s
        #define L a[j + 1].l
        #define P a[j + 1].p
        ma[min(n + 1, S)] = -min(n + 1, S) * P;
        for(i=min(n, S - 1); i >= max(0, S - L); i--)
            ma[i] = max(ma[i + 1], F[j][i] - P * i);
    }
    cout << F[m][n];
    return 0;
}

Code mẫu của RR

//Written by Nguyen Thanh Trung
{$R+,Q+}
{$Mode objFPC}
uses math;
const
  FINP          =       '';
  FOUT          =       '';
  MAXN          =       16111;
  MAXK          =       111;
type
  Tworker       =       record l,s,p:longint; end;
var
  f1,f2         :       text;
  worker        :       array[1..MAXK] of Tworker;
  ln,d          :       array[0..MAXN] of longint;
  n,k           :       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;
    begin
      read(f1,n,k);
      for k:=1 to k do
        with worker[k] do
          read(f1,l,p,s);
    end;
procedure sort;
    var
      i,j:longint;
      temp:Tworker;
    begin
      for i:=1 to k-1 do
      for j:=i+1 to k do
        if worker[i].s>worker[j].s then
          begin
            temp:=worker[i];
            worker[i]:=worker[j];
            worker[j]:=temp;
          end;
    end;
procedure solve;
    var
      gh,i,w,now,kq:longint;
    begin
      for w:=1 to k do
        begin
          ln[worker[w].s]:=d[worker[w].s-1];
          now:=0;
          gh:=max(1,worker[w].s-worker[w].l+1);
          for i:=worker[w].s-1 downto gh do
            begin
              now+=worker[w].p;
              ln[i]:=max(d[i-1]+now,ln[i+1]);
            end;
          gh:=min(worker[w].s+worker[w].l-1,n);
          now:=0;
          for i:=worker[w].s to gh do
            begin
              now+=worker[w].p;
              d[i]:=max(d[i],ln[max(i-worker[w].l+1,1)]+now);
            end;
        end;
      kq:=0;
      for i:=1 to n do
        kq:=max(kq,d[i]);
      writeln(f2,kq);
    end;

begin
  openF;
  inp;
  sort;
  solve;
  closeF;
end.

Code mẫu của hieult

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <iostream>
#include <algorithm>

#include <ctime>
#include <deque>
#include <bitset>
#include <cctype>
#include <utility>
#include <cassert>

using namespace std;

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

#define Rep(i,n) for(int i = 0; i < (n); ++i)
#define Repd(i,n) for(int i = (n)-1; i >= 0; --i)
#define For(i,a,b) for(int i = (a); i <= (b); ++i)
#define Ford(i,a,b) for(int 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))

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> 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> 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 = (int) 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;
}

typedef pair<int, int> II;

const double PI = acos(-1.0);
const double eps = 1e-9;

const int dr[] = {0, +1, 0, -1};
const int dc[] = {+1, 0, -1, 0};

const int inf = (int)1e9 + 5;
const ll linf = (ll)1e16 + 5;
const ll mod = (ll)1e9 + 7;

struct Son{
    int l, s, cost;
    Son(){};
    Son(int _l, int _cost, int _s){
        l = _l; cost = _cost; s = _s;
    }
    bool operator <(const Son &S)const{
        return s < S.s;
    }
}A[205];

int f[16005][105], g[16005];
int n, k;

int main(){
//  freopen("in.txt", "r", stdin);

    cin >> n >> k;
    int l, cost, s;
    For(i, 1, k){
        scanf("%d %d %d", &l, &cost, &s);
        A[i] = Son(l, cost, s);
    }

    sort(A + 1, A + k + 1);

    ms(f, 0);
    For(run, 1, k){
        For(i, 0, n) f[i][run] = f[i][run - 1];
        ms(g, 0);
        Ford(i, A[run].s, max(A[run].s - A[run].l + 1, 1)){
            g[i] = max(g[i + 1], f[i - 1][run - 1] + (A[run].s - i + 1) * A[run].cost);
        }
        For(i, A[run].s, min(A[run].s + A[run].l - 1, n)){
            f[i][run] = max(f[i][run], g[max(1,i - A[run].l + 1)] + (i - A[run].s) * A[run].cost);
        }

        For(i, 1, n) f[i][run] = max(f[i][run], f[i - 1][run]);
//      For(i, 1, n) cout << f[i][run] << " "; puts("");
    }

    cout << f[n][k] << endl;

    return 0;
}