## Editorial for VM 08 Bài 16 - Xếp hình

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

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

program VBLOCKS;
uses    math;
const   maxn=100005;
fi='';
var     a,f,s1,s2:array[-2*maxn..maxn] of longint;
x,y,n,l,d,i,k,p,q:longint;
inp:text;
begin
assign(inp,fi);reset(inp);
for i:=1 to k do begin
end;
for i:=-2*n to 0 do a[i]:=2;
for i:=1 to n do if a[i]=1 then s1[i]:=s1[i-1]+1
else s1[i]:=s1[i-1];
for i:=-2*n to n do if a[i]=2 then s2[i]:=s2[i-1]+1
else s2[i]:=s2[i-1];
for i:=1 to n do begin
f[i]:=low(longint);
if a[i]<>1 then f[i]:=max(f[i],f[i-1]);
p:=s2[i]-s2[i-l];q:=s1[i-l]-s1[i-l-d];
if (p=0) and (q=0) then f[i]:=max(f[i],f[i-l-d]+1);
end;
if f[n]>0 then write(f[n])
else write(-1);
end.


{$R+,Q+} PROGRAM VBLOCKS; CONST FINP=''; FOUT=''; maxn=100001; VAR n,s,d:longint; max,f:array[0..maxn] of longint; sl:array[1..2,0..maxn] of longint; c:array[1..maxn] of longint; a:array[1..maxn] of byte; procedure readInput; var f:text; i,m,u:longint; begin assign(f,FINP); reset(f); readln(f,n,s,d); readln(f,m); for i:=1 to m do begin readln(f,u,a[u]); end; close(f); end; procedure prepare; var i:longint; begin for i:=1 to n do if a[i]=1 then begin sl[1,i]:=sl[1,i-1]+1; sl[2,i]:=sl[2,i-1]; end else if a[i]=2 then begin sl[1,i]:=sl[1,i-1]; sl[2,i]:=sl[2,i-1]+1; end else begin sl[1,i]:=sl[1,i-1]; sl[2,i]:=sl[2,i-1]; end; for i:=1 to n do begin f[i]:=-1; max[i]:=-1; end; end; function get(u,k:longint):longint; begin if u<=0 then get:=0 else get:=sl[k,u]; end; procedure updateBIT(u:longint); var v:longint; begin inc(c[u]); v:=u+u and (u xor (u-1)); if v<=n then updateBIT(v); end; function getBIT(u:longint):longint; var v,kq:longint; begin if u<=0 then kq:=0 else kq:=c[u]; v:=u-u and (u xor (u-1)); if (v>0) and (u>0) then kq:=kq+getBIT(v); getBIT:=kq; end; procedure solve; var i:longint; begin max[0]:=-1; f[0]:=-1; for i:=1 to n do begin if (get(i-1,1)-get(i-d-1,1)>0) or (get(i+s-1,2)-get(i-1,2)>0) or (get(i+s+d-1,1)-get(i+s-1,1)>0) or (i+s-1>n) then f[i]:=-1 else if i-d-s>0 then begin if max[i-d-s]>=0 then f[i]:=max[i-d-s]+1 else f[i]:=1; end else if sl[1,i-1]>0 then f[i]:=-1 else f[i]:=1; if f[i]>max[i-1] then max[i]:=f[i] else max[i]:=max[i-1]; if f[i]>0 then updateBIT(i); end; end; procedure writeOutput; var f:text; begin assign(f,FOUT); rewrite(f); writeln(f,max[n]); close(f); end; procedure refine; var i,u,count:longint; begin for i:=1 to n do if (a[i]=1) and (getBIT(i)-getBIT(i-s)=0) then begin max[n]:=-1; exit; end; count:=0; for i:=1 to n do if a[i]=1 then inc(count); for i:=1 to n do if a[i]=1 then begin u:=i; break; end; i:=u; while i<n do begin inc(i); if a[i]=1 then begin if i-u+1<=s then dec(count); u:=i; end; end; if count>max[n] then max[n]:=-1; end; BEGIN readInput; prepare; solve; refine; writeOutput; 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 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 ld PI = acos(-1.0); const ld 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; #define maxn 100005 int n, s, t; int a[maxn], d[maxn], e[maxn], f[maxn]; int main() { // freopen("in.txt", "r", stdin); cin >> n >> s >> t; int k; cin >> k; int x, id; ms(a, 0); ms(d, 0); ms(e, 0); Rep(run, k){ scanf("%d %d", &x, &id); a[x] = id; } For(i, 1, n) { d[i] = d[i - 1]; e[i] = e[i - 1]; if(a[i] == 2) d[i]++; if(a[i] == 1) e[i]++; } ms(f, -0x3f); f[0] = 0; For(i, 1, n){ if(a[i] != 1) f[i] = f[i - 1]; if(i >= s && d[i] == d[i - s] && e[i - s] == e[max(0, i - s - t)]){ f[i] = max(f[i], f[max(0, i - s - t)] + 1); } } cout << max(-1, f[n]) << endl; return 0; }  #### Code mẫu của ll931110 {$MODE DELPHI}
Program VBLOCKS2;
Const
input  = '';
output = '';
maxn = 100000;
Var
F: array[-maxn..maxn] of integer;
a: array[-maxn..maxn,1..2] of integer;
l,s,d,k: integer;

Procedure init;
Var
fi: text;
i,u,v: integer;
Begin
Assign(fi, input);
Reset(fi);

Fillchar(a, sizeof(a), 0);

For i:= 1 to k do
Begin
inc(a[u,v]);
End;

For u:= 1 to l do
Begin
a[u,1]:= a[u,1] + a[u - 1,1];
a[u,2]:= a[u,2] + a[u - 1,2];
End;

Close(fi);

Fillchar(F, sizeof(F), 0);
End;

Procedure solve;
Var
i,x,y: integer;
Begin
For i:= s to l do
Begin
F[i]:= 0;
If a[i,1] - a[i - 1,1] = 0 then F[i]:= F[i - 1];

x:= i - s - d;
y:= i - s;
If (a[i,2] - a[y,2] = 0) and (a[y,1] - a[x,1] = 0)
and (F[i] < F[x] + 1) then F[i]:= F[x] + 1;
End;
End;

Procedure printresult;
Var
fo: text;
Begin
Assign(fo, output);
Rewrite(fo);
If F[l] = 0 then writeln(fo, -1) else writeln(fo, F[l]);
Close(fo);
End;

Begin
init;
solve;
printresult;
End.


#### Code mẫu của khuc_tuan

#include <iostream>
using namespace std;

int L, S, D;
int K;
int q[100010];
int prev[100010][2];
int F[100010], G[100010];

int main() {
scanf("%d%d%d", &L, &S, &D);
scanf("%d", &K);
for(int i=0;i<K;++i) {
int u, v;
scanf("%d%d", &u, &v);
if(q[u]>0 && q[u]!=v) {
cout << -1 << endl;
return 0;
}
else q[u] = v;
}
for(int i=1;i<=L;++i) {
prev[i][0] = prev[i-1][0];
prev[i][1] = prev[i-1][1];
if(q[i]>0) prev[i][q[i]-1] = i;
}
memset( F, -1, sizeof(F));
memset( G, -1, sizeof(G));
for(int i=1;i<=L;++i) {
if(i>=S) {
int st = i - S + 1;
int tr = st - D;
if(prev[i][1]<st && (prev[st-1][0]<tr || prev[st-1][0]==0)) {
if(tr<=1) F[i] = 1;
else {
if(prev[tr-1][0]==0) F[i] = 1;
if(G[tr-1]!=-1) F[i] = 1 + G[tr-1];
}
}
}
if(q[i]==1) G[i] = F[i];
else G[i] = max( F[i], G[i-1]);
}
cout << G[L] << endl;
//system("pause");
return 0;
}