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

uses math;
const fi='';
      maxn=100010;
type ar=array[0..maxn] of longint;
var n,xx,yy,mx:longint;
    a,b,c,y,d:ar;
    col:array[0..maxn] of int64;
    re:int64;

procedure rf;
var i:longint;
begin
     read(xx,yy,n);
     for i:=1 to n do
     begin
          read(a[i],b[i],c[i]);
          y[i]:=b[i]; d[i]:=i;
     end;
end;

procedure sort(l,r:longint);
var i,j,x,t:longint;
begin
     i:=l; j:=r; x:=y[(i+j) shr 1];
     repeat
           while y[i]<x do i:=i+1;
           while y[j]>x do j:=j-1;
           if i<=j then
           begin
                t:=y[i]; y[i]:=y[j]; y[j]:=t;
                t:=d[i]; d[i]:=d[j]; d[j]:=t;
                i:=i+1; j:=j-1;
           end;
     until i>j;
     if i<r then sort(i,r);
     if l<j then sort(l,j);
end;

procedure discr;
var i:longint;
begin
     sort(1,n);
     mx:=1; b[d[1]]:=1;
     for i:=2 to n do
     begin
          if y[i]>y[mx] then
          begin
               inc(mx);
               y[mx]:=y[i];
          end;
          b[d[i]]:=mx;
     end;
end;

procedure sortt(l,r:longint);
var i,j,x,y,t:longint;
begin
     i:=l; j:=r; x:=a[(i+j) shr 1]; y:=b[(i+j) shr 1];
     repeat
           while (a[i]<x) or ((a[i]=x) and (b[i]<y)) do i:=i+1;
           while (a[j]>x) or ((a[j]=x) and (b[j]>y)) do j:=j-1;
           if i<=j then
           begin
                t:=a[i]; a[i]:=a[j]; a[j]:=t;
                t:=b[i]; b[i]:=b[j]; b[j]:=t;
                t:=c[i]; c[i]:=c[j]; c[j]:=t;
                i:=i+1; j:=j-1;
           end;
     until i>j;
     if i<r then sortt(i,r);
     if l<j then sortt(l,j);
end;

procedure update(x:longint;val:int64);
begin
     while x<=mx do
     begin
          if val<=col[x] then exit;
          col[x]:=val;
          x:=x+x and (-x);
     end;
end;

function get(x:longint):int64;
var r:int64;
begin
     r:=0;
     while x>0 do
     begin
          r:=max(r,col[x]);
          x:=x-x and (-x);
     end;
     exit(r);
end;

procedure pr;
var i:longint; row,x:int64;
begin
     re:=0; row:=0; i:=1;
     while (a[i]<1) or ((a[i]=1) and (b[i]<1)) do i:=i+1;
     while i<=n do
     begin
          if (i=1) or (a[i]<>a[i-1]) then row:=0;
          x:=get(b[i]);
          row:=max(row,x)+c[i];
          update(b[i],row);
          re:=max(re,row);
          inc(i);
     end;
     writeln(re);
end;

begin
     assign(input,fi); reset(input);
     rf;
     discr;
     sortt(1,n);
     pr;
     close(input);
end.

Code mẫu của ladpro98

program MBUS;
uses    math;
const   maxn=100005;
        fi='';
type    e=record
                x,z,dy:longint;
        end;
        e2=record
                v,p:longint;
        end;
var     a:array[1..maxn] of e;
        col:array[0..maxn] of e2;
        bit:array[1..maxn] of int64;
        x,y,n,d:longint;
        res:int64;

procedure input;
var     inp:text;
        i:longint;
begin
        assign(inp,fi);reset(inp);
        readln(inp,x,y,n);
        for i:=1 to n do begin
                readln(inp,a[i].x,col[i].v,a[i].z);
                col[i].p:=i;
        end;
        close(inp);
end;

procedure sortA(l,r:longint);
var     i,j:longint;
        p,t:e;
begin
        if l>=r then exit;
        i:=l;j:=r;
        p:=a[random(r-l+1)+l];
        repeat
                while (a[i].x<p.x) or ((a[i].x=p.x) and (a[i].dy<p.dy)) do inc(i);
                while (a[j].x>p.x) or ((a[j].x=p.x) and (a[j].dy>p.dy)) do dec(j);
                if i<=j then begin
                        if i<j then begin
                                t:=a[i];
                                a[i]:=a[j];
                                a[j]:=t
                        end;
                        inc(i);dec(j);
                end;
        until i>j;
        sortA(l,j);sortA(i,r);
end;

procedure sortCol(l,r:longint);
var     i,j:longint;
        p,t:e2;
begin
        if l>=r then exit;
        i:=l;j:=r;
        p:=col[random(r-l+1)+l];
        repeat
                while (col[i].v<p.v) do inc(i);
                while (col[j].v>p.v) do dec(j);
                if i<=j then begin
                        if i<j then begin
                                t:=col[i];
                                col[i]:=col[j];
                                col[j]:=t;
                        end;
                        inc(i);dec(j);
                end;
        until i>j;
        sortCol(l,j);sortCol(i,r);
end;

procedure discrete;
var     i:longint;
begin
        sortCol(1,n);
        col[0].v:=-1;
        for i:=1 to n do begin
                if col[i].v<>col[i-1].v then inc(d);
                a[col[i].p].dy:=d;
        end;
end;

procedure update(i,v:longint);
begin
        while i<=d do begin
                bit[i]:=max(bit[i],v);
                i:=i+i and (-i);
        end;
end;

function get(i:longint):longint;
var     t:longint;
begin
        t:=0;
        while i>0 do begin
                t:=max(t,bit[i]);
                i:=i-i and (-i);
        end;
        exit(t);
end;

procedure dp;
var     i:longint;
        t:int64;
begin
        sortA(1,n);
        for i:=1 to n do begin
                t:=get(a[i].dy)+a[i].z;
                if bit[a[i].dy]<t then
                update(a[i].dy,t);
                res:=max(res,t);
        end;
end;

begin
        input;
        discrete;
        dp;
        write(res);
end.

Code mẫu của RR

#include <iostream>
#include <algorithm>
#include <map>
#define MAXN 100111
#define F first
#define S second
#define _(u) (u&(-u))
#define FOR(i,a,b) for(long i=a; i<=b; i++)
#define FORV(i,v)  for(typeof(v.begin()) i=v.begin(); i!=v.end(); i++)
using namespace std;

long n,X,Y,bit[MAXN],f[MAXN];
pair<pair<long,long>,long> a[MAXN];
map<long,long> m;

void inp() {
    scanf("%ld %ld %ld",&X,&Y,&n);
    FOR(i,1,n) {
        scanf("%ld %ld %ld",&a[i].F.F,&a[i].F.S,&a[i].S);
        if (a[i].F.F<1 || a[i].F.S<1) a[i].S=0;
    }

    m[1]=1; m[Y]=0;
    FOR(i,1,n) m[a[i].F.S]=0;
    FORV(i,m) {
        typeof(i) j=i; j--;
        i->second=j->second+1;
    }

    FOR(i,1,n) a[i].F.S=m[a[i].F.S];
    Y=m[Y];

    sort(a+1,a+n+1);
}

long get(long u) {
    if (u<=0) return 0;
    long v=u-_(u);
    return max(bit[u],get(v));
}

void update(long k,long u) {
    bit[u]=max(bit[u],k);
    long v=u+_(u);
    if (v<=n+1) update(k,v);
}

void solve() {
    long res=0;
    FOR(i,1,n) {
        f[i]=get(a[i].F.S)+a[i].S;
        update(f[i],a[i].F.S);
        res=max(res,f[i]);
    }
    printf("%ld",res);
}

int main() {
//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);
    inp();
    solve();
    return 0;
}

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 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[] = {0, +1, 0, -1};
const int dc[] = {+1, 0, -1, 0};
const int inf = (int)1e9 + 5;
const ll linf = (ll)1e16 + 5;
const double eps = 1e-9;
const ll mod = 100000007;
typedef pair<int, int> II;

#define maxn 100005
#define maxe 100005

ll f[maxn];
vector<int> vx, vy;
pair<II, II> P[maxn];

int X, Y, n;

void update(int u, ll x){
    for(int i = u; i < maxn; i += i & -i){
        f[i] = max(f[i], x);
    }
}

ll get(int u){
    ll res = 0;
    for(int i = u; i > 0; i -= i & -i){
        res = max(res, f[i]);
    }
    return res;
}

int main() {
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    gi(X); gi(Y); gi(n);
    vx.resize(n + 2); vy.resize(n + 2);
    ms(f, 0);
    vx[0] = (X); vy[0] = (Y); vx[1] = (1); vy[1] = (1);
    int x, y;
    ll c, t;

    Rep(i, n){
        gi(P[i].fi.fi); gi(P[i].fi.se); gi(P[i].se.fi);
        vx[i + 2] = (P[i].fi.fi); vy[i + 2] = (P[i].fi.se);
    }
    P[n] = mp(mp(1, 1), mp(0, 0));
    P[n + 1] = mp(mp(X, Y), mp(0, 0)); 

    sort(all(vx)); sort(all(vy)); sort(P, P + n + 2);
    ll res;
    For(i, 1, n + 1){
        y = lower_bound(all(vy), P[i].fi.se) - vy.begin() + 1;
        t = get(y);
        update(y, t + P[i].se.fi);
        if(i == n + 1) res = t + P[i].se.fi;
    }

    cout << res;
    return 0;
}

Code mẫu của ll931110

#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <stack>
#include <queue>
#include <vector>
#include <utility>
using namespace std;

int x[100010],y[100010],c[100010],tx[100010];
vector< pair<int,int> > a;
vector< pair<int,int> > v[100010];
int n,m,k;

void update(int p,int q)
{
    while (p <= 100000)
    {
        tx[p] = max(tx[p],q);  p += (p & -p);
    };
};

int calc(int p)
{
    int q = 0;
    while (p)
    {
        q = max(q,tx[p]);  p -= (p & -p);
    };
    return q;
};

int main()
{
//    freopen("bus.in","r",stdin);
//    freopen("bus.ou","w",stdout);
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= k; i++) 
      scanf("%d%d%d", &x[i], &y[i], &c[i]);

    for (int i = 1; i <= k; i++)
      a.push_back(make_pair(x[i],i));
    sort(a.begin(),a.end());
    x[a[0].second] = 1;  int cc = 1;
    for (int i = 1; i < a.size(); i++) 
    {
        if (a[i].first > a[i - 1].first) cc++;
        x[a[i].second] = cc;
    };

    a.clear();
    for (int i = 1; i <= k; i++)
      a.push_back(make_pair(y[i],i));
    sort(a.begin(),a.end());
    y[a[0].second] = 1;  cc = 1;
    for (int i = 1; i < a.size(); i++) 
    {
        if (a[i].first > a[i - 1].first) cc++;
        y[a[i].second] = cc;
    };

    for (int i = 1; i <= k; i++) v[x[i]].push_back(make_pair(y[i],i));
    for (int i = 1; i <= 100000; i++) sort(v[i].begin(),v[i].end());
    int ret = 0;
    memset(tx,0,sizeof(tx));
    for (int i = 1; i <= 100000; i++)
      for (int j = 0; j < v[i].size(); j++)
      {
            int u = v[i][j].first;  int pos = v[i][j].second;
//            cout << i << ' ' << u << ' ' << pos << endl;
            int tmp = calc(u);
            ret = max(ret,tmp + c[pos]);
            update(u,tmp + c[pos]);            
        };
    printf("%d\n", ret);
};

Code mẫu của khuc_tuan

#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define Rep(i,n) for(int i=0;i<(n);++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 fi first
#define se second
#define pb push_back
#define MP make_pair

const int maxn=100010;

struct Data{
    int x,y,z;
};

int cmp(Data a,Data b){
    if(a.x==b.x)return a.y<b.y;
    else return a.x<b.x;
}

int X,Y,n,nt;
int T[maxn];
Data a[maxn];
long long F[maxn];
long long B[maxn];

int main() {
    scanf("%d%d%d",&X,&Y,&n);
    Rep(i,n)scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
    a[n].x=X,a[n].y=Y,a[n].z=0;
    ++n;
    Rep(i,n)T[i]=a[i].y;
    sort(T,T+n);
    nt=unique(T,T+n)-T;
    sort(a,a+n,cmp);
    Rep(i,n){
        int id=lower_bound(T,T+nt,a[i].y)-T+1;
        int id2=id;
        long long r=0;
        for(;id>0;id&=(id-1))r=max(r,B[id]);
        r+=a[i].z;
        F[i]=r;
        for(;id2<=nt;id2+=id2&(-id2))B[id2]=max(B[id2],r);
    }
    Ford(i,n-1,0)if(a[i].x==X&&a[i].y==Y){cout<<F[i]<<endl;break;}
    return 0;   
}