## Editorial for Cắt gỗ

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

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

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

int value[51],a[51],n,g[51][51],f[51][101],ans;

int main()
{
int x,y,m;
cin >> n;
for (int i=1;i<=n;i++) cin >> a[i];
cin >> m;
while (m--) cin >> x >> y, value[x]=max(value[x],y);
// precalc for each bar
for (int i=1;i<=50;i++) g[i][0]=-1000000;
for (int i=1;i<=50;i++)
for (int j=1;j<=i;j++)
for (int ii=0;ii<i;ii++)
g[i][j]=max(g[i][j],g[ii][j-1]+value[i-ii]);
// dp
for (int i=1;i<=n;i++)
for (int j=1;j<=a[i];j++)
for (int k=j-1;k<=100;k++)
f[i][k]=max(f[i][k],f[i-1][k-j+1]+g[a[i]][j]);
for (int k=0;k<=100;k++) ans=max(ans,f[n][k]-k*(k+1)/2);
cout << ans << endl;
}


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
const int N = 53;
const int lim = 73;
using namespace std;

int F[N][N][lim];
int res, n, m;
int a[N], val[N];

void maximize(int &a, int b)
{a = a > b ? a : b; res = res > a ? res : a;}

int main() {
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i];
cin >> m;
int d, v;
for(int i = 1; i <= m; i++) {
cin >> d >> v;
val[d] = v;
}
memset(F, 255, sizeof F);
F[1][a[1]][0] = 0;
for(int i = 1; i <= n; i++)
for(int j = a[i]; j; j--)
for(int k = 0; k < lim - 1; k++)
if (F[i][j][k] != -1) {
for(int t = 1; t < j; t++)
maximize(F[i][j - t][k + 1], F[i][j][k] + val[t] - k - 1);
maximize(F[i + 1][a[i + 1]][k], F[i][j][k] + val[j]);
}
cout << res;
return 0;
}


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

{\$R+,Q+}
PROGRAM CATGO;
CONST
FINP='';
FOUT='';
max=52;
VAR
t,n,m:integer;
gt:array[0..max] of longint;
c:array[1..max] of longint;
d:array[1..max,0..max*max] of longint;
kq:array[0..max,0..max*max] of longint;
var
f:text;
u,i:integer;
begin
assign(f,FINP); reset(f);
for i:=1 to n do
for i:=1 to m do
begin
d[u,0]:=gt[u];
end;
close(f);
end;
function max2(a,b:longint):longint;
begin
if a>b then max2:=a else max2:=b;
end;
procedure writeOutput;
var
f:text;
begin
assign(f,FOUT); rewrite(f);
for i:=0 to t do
close(f);
end;
procedure QHD1;
var
i,j,k:integer;
begin
for i:=1 to max do
for j:=1 to i-1 do
for k:=1 to i-1 do
d[i,j]:=max2(d[i,j],d[k,j-1]+gt[i-k]);
end;
function min2(a,b:longint):longint;
begin
if a<b then min2:=a else min2:=b;
end;
procedure QHD2;
var
i,j,k,u,g,l,gg:integer;
begin
t:=0;
for i:=1 to n do
begin
u:=c[i]; l:=t; t:=t+u-1;
gg:=min2(t,max);
for j:=0 to gg do
begin
g:=min2(l,j);
g:=min2(max,g);
for k:=0 to g do
kq[i,j]:=max2(kq[i,j],kq[i-1,k]+d[u,j-k]+k*(k+1) div 2-j*(j+1) div 2);
end;
end;
end;
BEGIN
QHD1;
QHD2;
writeOutput;
END.


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

#include <stdio.h>
//#include <conio.h>
int n,m,kt[51],dai[51],gia[51];
int d[51][51],flag[51],f[51][53];

int main()
{
//freopen("CATGO_10.in","r",stdin);
for(int i = 0;i<=50;i++)
{
flag[i]=0;
for(int j = 0;j<=50;j++)
{
d[i][j]=0;
f[i][j]=0;
}
}

scanf("%d",&n);
for(int i = 1;i<=n;i++)
scanf("%d",&kt[i]);
scanf("%d",&m);
for(int i = 1;i<=m;i++)
{
scanf("%d %d",&dai[i],&gia[i]);
flag[dai[i]]=i;
}
for(int i = 1;i<=50;i++)
for(int j = 0;j<=50;j++)
{
if(j==0)
{
if( flag[i]!=0)
d[i][j]=gia[flag[i]];
}
else
{
int max=0;
for(int k = 1;k<=i-1;k++)
if(d[k][j-1]+d[i-k][0]>max)
max = d[k][j-1]+d[i-k][0];
d[i][j]=max;
}
//if(i==10) printf("%d %d %d\n",j,d[i][j],flag[10]);
}
for(int i = 1;i<=n;i++)
for(int j = 0;j<=52;j++)
{
if(i==1)
f[i][j]=d[kt[i]][j];
else
{
int max = 0;
for(int k = 0;k<=j;k++)
if(f[i-1][k]+d[kt[i]][j-k]>max)
max = f[i-1][k]+d[kt[i]][j-k];
f[i][j] = max;
}
}
int Max = 0;
for(int i=0;i<=52;i++)
if(f[n][i]-i*(i+1)/2>Max)
{
Max = f[n][i]-i*(i+1)/2;
// printf("%d %d %d\n",i,f[n][i],Max);
}
printf("%d",Max);
//getch();
}


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

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>
typedef long long ll;
using namespace std;

int n,m;
int g[52][52],f[52][502];
int a[52],len[52],val[52];

int main()
{
//    freopen("catgo.in","r",stdin);
//    freopen("catgo.ou","w",stdout);
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
scanf("%d", &m);
for (int i = 0; i < m; i++) scanf("%d %d", &len[i], &val[i]);

memset(g,0,sizeof(g));
for (int i = 0; i < m; i++) g[len[i]][0] = max(g[len[i]][0],val[i]);
for (int j = 1; j < 50; j++)
for (int i = 1; i <= 50; i++)
for (int t = 0; t < m; t++) if (i >= len[t]) g[i][j] = max(g[i][j],g[i - len[t]][j - 1] + val[t]);

memset(f,0,sizeof(f));
for (int i = 1; i <= n; i++)
for (int j = 0; j <= 500; j++)
for (int t = 0; t < a[i] && t <= j; t++) f[i][j] = max(f[i][j],f[i - 1][j - t] + g[a[i]][t]);

int best = 0;
for (int i = 0; i <= 500; i++) best = max(best,f[n][i] - i * (i + 1) / 2);
printf("%d\n", best);
};


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

import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; ++i)
a[i] = sc.nextInt();
int m = sc.nextInt();
int[] v = new int[55];
for (int i = 0; i < m; ++i) {
int x = sc.nextInt();
v[x] = sc.nextInt();
}
int[][] f = new int[55][55];
for (int i = 0; i < f.length; ++i)
for (int j = 0; j < f[i].length; ++j)
if (j == 0)
f[i][j] = v[i];
else
for (int len = 1; len < i; ++len)
f[i][j] = Math.max(f[i][j], f[i - len][j - 1] + v[len]);
int[][] g = new int[n][1000];
for (int i = 0; i < n; ++i)
for (int j = 0; j < g[i].length; ++j)
for (int t = 0; t < 55 && t <= j; ++t)
g[i][j] = Math.max(g[i][j], (i == 0 ? 0 : g[i - 1][j - t])
+ f[a[i]][t]);
int total = 0;
int res = 0;
for (int x = 0; x < 1000; ++x) {
total += x;
res = Math.max(res, g[n - 1][x] - total);
}
System.out.println(res);
}
}