Hướng dẫn giải của BARICA
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
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 maxn=100010; var n,k:longint; x,y,a,d,f:array[1..maxn] of longint; maxcol:array[0..maxn] of longint; procedure rf; var i:longint; begin read(n,k); for i:=1 to n do begin read(x[i],y[i],a[i]); d[i]:=i; end; end; procedure sort(l,r:longint); var i,j,t,u,v:longint; begin i:=l; j:=r; t:=x[(i+j) shr 1]; v:=y[(i+j) shr 1]; repeat while (x[i]<t) or ((x[i]=t) and (y[i]<v)) do i:=i+1; while (x[j]>t) or ((x[j]=t) and (y[j]>v)) do j:=j-1; if i<=j then begin u:=d[i]; d[i]:=d[j]; d[j]:=u; u:=x[i]; x[i]:=x[j]; x[j]:=u; u:=y[i]; y[i]:=y[j]; y[j]:=u; u:=a[i]; a[i]:=a[j]; a[j]:=u; 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; function max(u,v:longint):longint; begin if u>v then max:=u else max:=v; end; procedure pr; var i,t,u,maxrow:longint; begin sort(1,n); for i:=1 to n do f[i]:=-1; for i:=0 to maxn div 3 do maxcol[i]:=-1; for t:=1 to n do if d[t]=1 then break; f[t]:=a[t]; maxcol[y[t]]:=a[t]; maxrow:=a[t]; inc(t); while true do begin if x[t]=x[t-1] then begin if maxrow>=k then f[t]:=max(f[t],maxrow-k+a[t]); end; if maxcol[y[t]]>=k then f[t]:=max(f[t],maxcol[y[t]]-k+a[t]); if x[t]=x[t-1] then maxrow:=max(maxrow,f[t]) else maxrow:=f[t]; maxcol[y[t]]:=max(maxcol[y[t]],f[t]); if d[t]=n then break; t:=t+1; end; writeln(f[t]); end; begin rf; pr; end.
Code mẫu của happyboy99x
#include<cstdio> #include<algorithm> using namespace std; const int N = 300000 + 5, XY = 100000 + 5, INF = 1000000000; struct plant { int x, y, f, id; bool operator < (const plant &o) const { return x < o.x || x == o.x && y < o.y; } } p[N]; int n, k, maxX[XY], maxY[XY], f[N]; void enter() { scanf("%d%d", &n, &k); for(int i = 1; i <= n; ++i) { scanf("%d%d%d", &p[i].x, &p[i].y, &p[i].f); p[i].id = i; } } void solve() { sort(p+1, p+n+1); f[0] = -INF; for(int i = 1; i <= n; ++i) { int id = p[i].id; f[id] = -INF; if(id == 1) f[id] = p[i].f; int xx = maxX[p[i].x], yy = maxY[p[i].y]; if(f[xx] >= k && f[xx] - k + p[i].f > f[id]) f[id] = f[xx] - k + p[i].f; if(f[yy] >= k && f[yy] - k + p[i].f > f[id]) f[id] = f[yy] - k + p[i].f; if(f[id] > f[xx]) maxX[p[i].x] = id; if(f[id] > f[yy]) maxY[p[i].y] = id; } printf("%d\n", f[n]); } int main() { enter(); solve(); return 0; }
Code mẫu của ladpro98
program baricavn;//dp uses math; type e=record x,y,p,s:longint; end; const maxn=300005; maxV=100005; fi=''; var a:array[1..maxn] of e; maxCol,maxRow:array[0..maxV] of longint; n,k:longint; procedure input; var inp:text; i:longint; begin assign(inp,fi); reset(inp); readln(inp,n,k); for i:=1 to n do begin readln(inp,a[i].x,a[i].y,a[i].s); a[i].p:=i; end; close(inp); end; procedure swap(i,j:longint); var t:e; begin t:=a[i]; a[i]:=a[j]; a[j]:=t; end; procedure sort(l,r:longint); var i,j:longint; p: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].y<p.y)) do inc(i); while (a[j].x>p.x) or ((a[j].x=p.x) and (a[j].y>p.y)) do dec(j); if i<=j then begin if i<j then swap(i,j); inc(i); dec(j); end; until i>j; sort(l,j); sort(i,r); end; procedure dp; var j,i,t,lx,ly:longint; begin for j:=1 to n do if a[j].p=1 then begin maxRow[a[j].x]:=a[j].s; maxCol[a[j].y]:=a[j].s; lx:=a[j].x;ly:=a[j].y; for i:=j+1 to n do if (a[i].x>=lx) and (a[i].y>=ly) then if max(maxRow[a[i].x],maxCol[a[i].y])>=k then begin t:=max(maxRow[a[i].x],maxCol[a[i].y])-k+a[i].s; if a[i].p=n then begin writeln(t); exit; end; maxRow[a[i].x]:=max(maxRow[a[i].x],t); maxCol[a[i].y]:=max(maxCol[a[i].y],t); end; end; end; begin input; sort(1,n); dp; end.
Code mẫu của RR
#include <cstdio> #include <cstdlib> #include <algorithm> #include <set> #define MAXN 300111 #define FOR(i,a,b) for(long i=a; i<=b; i++) #define S set< pair<long,long> > #define FORS(s,i) for(S::iterator i=s.begin(); i!=s.end(); i++) #define MP make_pair using namespace std; long n,k,targetu,targetv,startu,startv,maxX[MAXN],maxY[MAXN],f[MAXN]; pair< pair<long,long>,long> a[MAXN]; S s; void inp() { scanf("%ld %ld",&n,&k); FOR(i,1,n) scanf("%ld %ld %ld",&a[i].first.first,&a[i].first.second,&a[i].second); } void RR() { //Roi rac hoa theo truc X FOR(i,1,n) s.insert(MP(a[i].first.first,i)); long now=s.begin()->first,ind=1; a[s.begin()->second].first.first=1; FORS(s,i) if (i!=s.begin()) { if (i->first!=now) { ind++; now=i->first; } a[i->second].first.first=ind; } //Roi rac hoa theo truc Y s.clear(); FOR(i,1,n) s.insert(MP(a[i].first.second,i)); now=s.begin()->first; ind=1; a[s.begin()->second].first.second=1; FORS(s,i) if (i!=s.begin()) { if (i->first!=now) { ind++; now=i->first; } a[i->second].first.second=ind; } } void solve() { targetu=a[n].first.first; targetv=a[n].first.second; startu=a[1].first.first; startv=a[1].first.second; sort(a+1,a+n+1); FOR(i,1,n) { if (a[i].first.first==startu&&a[i].first.second==startv) { f[i]=a[i].second; maxX[a[i].first.first]=f[i]; maxY[a[i].first.second]=f[i]; } else { long temp=max(maxX[a[i].first.first],maxY[a[i].first.second])-k; if (temp>=0) temp+=a[i].second; else temp=0; f[i]=temp; maxX[a[i].first.first]>?=f[i]; maxY[a[i].first.second]>?=f[i]; } } FOR(i,1,n) if (a[i].first.first==targetu&&a[i].first.second==targetv) printf("%ld\n",f[i]); } int main() { #ifdef DEBUG freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif inp(); RR(); 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[] = {-1, 0, +1, 0}; const int dc[] = {0, +1, 0, -1}; 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 300005 pair<II, II> A[maxn]; int n, k, fx[maxn], fy[maxn], f[maxn]; int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); ms(f, -1); ms(fx, -1); ms(fy, -1); gi(n); gi(k); Rep(i, n){ gi(A[i].fi.fi); gi(A[i].fi.se); gi(A[i].se.fi); A[i].se.se = i + 1; } sort(A, A + n); bool flag = false; int x, y, num, id, t; Rep(i, n){ if(!flag && A[i].se.se != 1) continue; x = A[i].fi.fi; y = A[i].fi.se; num = A[i].se.fi; id = A[i].se.se; if(A[i].se.se == 1){ flag = true; fx[x] = max(fx[x], num); fy[y] = max(fy[y], num); continue; } t = max(fx[x], fy[y]); if(t < k) continue; fx[x] = max(fx[x], t - k + num); fy[y] = max(fy[y], t - k + num); if(id == n){ printf("%d", t - k + num); return 0; } } }
Code mẫu của ll931110
{$MODE DELPHI} program BARICAVN; uses math; const input = ''; output = ''; maxn = 300000; maxt = 100000; type rec = record x,y,val,pos: integer; end; var a: array[1..maxn] of rec; maxx,maxy: array[0..maxt] of integer; n,k: integer; procedure init; var f: text; i: integer; begin assign(f, input); reset(f); readln(f, n, k); for i := 1 to n do begin readln(f, a[i].x,a[i].y,a[i].val); a[i].pos := i; end; close(f); end; procedure swap(var u,v: rec); var z: rec; begin z := u; u := v; v := z; end; function lower(u,v: rec): boolean; begin lower := (u.x < v.x) or ((u.x = v.x) and (u.y < v.y)); end; procedure quicksort; procedure par(l,h: integer); var i,j: integer; p: rec; begin if l >= h then exit; i := l; j := h; p := a[random(h - l + 1) + l]; repeat while lower(a[i],p) do inc(i); while lower(p,a[j]) do dec(j); if i <= j then begin if i < j then swap(a[i],a[j]); inc(i); dec(j); end; until i > j; par(l,j); par(i,h); end; begin par(1,n); end; procedure solve; var f: text; i,t: integer; begin for i := 0 to maxt do begin maxx[i] := -maxn; maxy[i] := -maxn; end; i := 1; while a[i].pos <> 1 do inc(i); maxx[a[i].x] := a[i].val; maxy[a[i].y] := a[i].val; repeat inc(i); t := max(maxx[a[i].x],maxy[a[i].y]); if t >= k then t := t - k + a[i].val; if maxx[a[i].x] < t then maxx[a[i].x] := t; if maxy[a[i].y] < t then maxy[a[i].y] := t; until a[i].pos = n; assign(f, output); rewrite(f); writeln(f, t); close(f); end; begin init; quicksort; solve; end.
Bình luận