## Editorial for Khuyến mãi

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>
#define oo 100000000
using namespace std;

int f[1010][1010],n,x;

int main()
{
cin >> n;
for (int i=0;i<=n;i++)
for (int j=0;j<=n;j++)
f[i][j]=oo;
f[0][0]=0;
for (int i=0;i<n;i++)
{
cin >> x;
for (int j=0;j<=i;j++)
if (f[i][j]!=oo)
{
f[i+1][j+(x>100)]=min(f[i+1][j+(x>100)],f[i][j]+x);
if (j) f[i+1][j-1]=min(f[i+1][j-1],f[i][j]);
}
}
int ans=oo;
for (int j=0;j<=n;j++) ans=min(ans,f[n][j]);
cout << ans << endl;
}


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

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

#define N 1002
int f[N][N], a[N], n;

int main() {
scanf("%d",&n);
for(int i = 0; i < n; ++i) scanf("%d", a+i);
for(int i = n-1; i >= 0; --i)
for(int j = i; j >= 0; --j) {
if(i == n-1) f[i][j] = j == 0 ? a[i] : 0;
else f[i][j] = min(a[i] + f[i+1][a[i] > 100 ? j+1 : j],
j > 0 ? f[i+1][j-1] : INT_MAX);
}
printf("%d\n", f[0][0]);
return 0;
}


uses    math;
const   maxn=1111;
fi='';
oo=trunc(1e9);
var     inp:text;
n,i,j,res:longint;
a:array[0..maxn] of longint;
f:array[0..maxn,0..maxn] of longint;
begin
assign(inp,fi);reset(inp);
for i:=1 to n do readln(inp,a[i]);
for j:=1 to n+1 do f[0,j]:=oo;
for i:=1 to n do begin
f[i,0]:=min(f[i-1,1],f[i-1,0]+a[i]);
for j:=1 to i do
if a[i]>100 then f[i,j]:=min(f[i-1,j+1],f[i-1,j-1]+a[i])
else    f[i,j]:=min(f[i-1,j+1],f[i-1,j]+a[i]);
for j:=i+1 to n+1 do f[i,j]:=oo;
end;
res:=oo;
for i:=0 to n do res:=min(res,f[n,i]);
write(res);
end.


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

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <complex>

#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 REP(i,a) for(int i = 0; i < a; ++i)
#define MP make_pair
#define PB push_back

using namespace std;

int n, a[1011], f[1011][1011];

void up(int &a, int b) {
if (b < 0) return ;
if (a < 0) a = b;
else a = min(a, b);
}

int main() {
scanf("%d", &n); FOR(i,1,n) scanf("%d", &a[i]);
memset(f, -1, sizeof f);
f[0][0] = 0;
FOR(i,0,n-1) FOR(j,0,i) if (f[i][j] >= 0) {
if (j > 0) {
up(f[i+1][j-1], f[i][j]);
}
up(f[i+1][j + (a[i+1] > 100 ? 1 : 0)], f[i][j] + a[i+1]);
}

int res = 1000111000;
FOR(j,0,n) up(res, f[n][j]);
cout << res << endl;
return 0;
}


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

#include<cstdio>
#include<cmath>
#include<math.h>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
#define ep 0.00001
#define maxn 1000
#define oo 2000000001
#define modunlo 111539786
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
//#define g 9.81
double const PI=4*atan(1.0);

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;

int n, f[maxn + 5][maxn + 5], a;

int main(){

// freopen("input.in","r",stdin);
// freopen("output.out","w",stdout);
scanf("%d",&n);
for(int i = 0; i <= n+2; i++) for(int j = 0; j <= n+2; j++) f[i][j] = oo;
f[0][0] = 0;
int kq = oo;
if(n == 0) kq = 0;
for(int i = 1; i <= n; i++){
scanf("%d",&a);
for(int j = 0; j <= i; j++){
f[i][j] = min(f[i][j],f[i-1][j+1]);
if(a > 100){
if(j > 0) f[i][j] = min(f[i][j], f[i-1][j-1] + a);
}
else f[i][j] = min(f[i][j],f[i-1][j] + a);
if( i == n) kq = min(kq, f[i][j]);
}
}
printf("%d",kq);
}