## Editorial for VOI 06 Bài 1 - Chọn ô

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

const fi='';
fo='';
maxn=10000;
r:array[1..8] of longint=(0,1,2,4,5,8,9,10);
p:array[0..3] of longint=(1,2,4,8);
var n,re:longint;
b:array[0..1,1..8] of longint;
a:array[0..3,1..maxn] of longint;
tr:array[1..maxn,1..8] of longint;
kt:boolean;

procedure rf;
var i,j:longint;
begin
assign(input,fi);
reset(input);
read(n);
for i:=0 to 3 do
for j:=1 to n do
read(a[i,j]);
close(input);
end;

procedure pr;
var i,j,k,t,q,max:longint;
begin
fillchar(b,sizeof(b),0);
kt:=true;
for i:=1 to 8 do
for j:=0 to 3 do
if r[i] or p[j]=r[i] then
b[1,i]:=b[1,i]+a[j,1];
t:=1;
for i:=2 to n do
begin
t:=i mod 2;
for j:=1 to 8 do
begin
b[t,j]:=-maxlongint;
for k:=1 to 8 do
if r[j] and r[k] = 0 then
begin
max:=b[1-t,k];
for q:=0 to 3 do
if r[j] or p[q] = r[j] then
max:=max+a[q,i];
if max>b[t,j] then
begin
b[t,j]:=max;
tr[i,j]:=k;
end;
end;
end;
end;
re:=b[t,1]; k:=1;
for i:=2 to 8 do
if b[t,i]>re then
begin
re:=b[t,i];
k:=i;
end;
i:=n;
if k=1 then
begin
while (k=1) and (i>0) do
begin
k:=tr[i,k];
dec(i);
end;
if (i=0) then kt:=false;
end;
end;

procedure wf;
var i,j:longint;
begin
assign(output,fo);
rewrite(output);
if not kt then
begin
re:=-maxlongint;
for i:=0 to 3 do
for j:=1 to n do
if a[i,j]>re then re:=a[i,j];
end;
write(re);
close(output);
end;

begin
rf;
pr;
wf;
end.


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

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define sz(a) int((a).size())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); it != _e; ++it)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i)
#define repd(i,n) for(int i = (n)-1; i >= 0; --i )
#define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i)
#define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i)

#define INF 1000000000
#define N 10005

int a[4][N], n, f[N][11];
int sts[] = {0,1,2,4,5,8,9,10};

int main() {
//freopen( "input.txt", "r", stdin );
//freopen( "output.txt", "w", stdout );
scanf( "%d", &n ); rep(i, 4) fo(j,1,n) scanf( "%d", &a[i][j] );
fo(j,1,n) {
rep(st, 8) {
rep(i,4) if(sts[st] & (1<<i)) f[j][sts[st]] += a[i][j];
int mx = INT_MIN;
rep(st2, 8) if((sts[st] | sts[st2])==(sts[st] ^ sts[st2]))
mx = max( f[j-1][sts[st2]], mx );
f[j][sts[st]] += mx;
}
}
int mx = INT_MIN;
rep(st, 8) mx = max(f[n][sts[st]], mx);
int mx2 = INT_MIN;
rep(i,4) fo(j,1,n) mx2 = max(mx2, a[i][j]);
printf( "%d\n", mx2 < 0 ? mx2 : mx );
return 0;
}


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

program qbselect;
uses    math;
const   fi='';
var     com:array[0..15,0..15] of boolean;
can:array[0..15] of boolean;
a:array[1..10001,1..4] of longint;

f,sum:array[0..10001,0..15] of longint;
bit:array[0..15,1..4] of longint;
n:longint;

procedure input;
var     inp:text;
var     i,j:longint;
begin
assign(inp,fi);
reset(inp);
readln(inp,n);
for j:=1 to 4 do
for i:=1 to n do
read(inp,a[i,j]);
close(inp);
end;

function getbit(n,i:longint):longint;
begin
exit((n shr (i-1)) and 1);
end;

procedure init;
var     i,j,k:longint;
begin
fillchar(can,sizeof(can),true);
fillchar(com,sizeof(com),true);
for i:=1 to n do
for j:=0 to 15 do
f[i,j]:=low(longint);

for i:=0 to 15 do
for j:=1 to 4 do
bit[i,j]:=getbit(i,j);

for i:=1 to n do
for j:=0 to 15 do
begin
for k:=1 to 4 do
inc(sum[i,j],bit[j,k]*a[i,k]);
end;
for i:=0 to 15 do
begin
for j:=1 to 3 do
if (getbit(i,j) = 1) and (getbit(i,j+1) = 1) then
can[i]:=false;
end;

for i:=0 to 15 do
for j:=0 to 15 do
begin
if (not can[i]) or (not can[j]) then
begin
com[i,j]:=false;
continue;
end;

for k:=1 to 4 do
if (getbit(i,k) = 1) and (getbit(j,k)=1) then
com[i,j]:=false;
end;

end;

procedure dp;
var     i,j,k:longint;
begin
for i:=1 to n do
begin
for j:=0 to 15 do
begin

if not can[j] then continue;
for k:=0 to 15 do
if com[j,k] then
f[i,j]:=max(f[i,j],f[i-1,k]+sum[i,j]);
end;
end;
end;

procedure output;
var     res,i,j:longint;
begin

res:=low(longint);
for i:=0 to 15 do
res:=max(res,f[n,i]);
if res<>0 then
write(res)
else
begin
res:=a[1,1];
for i:=1 to n do
for j:=1 to 4 do
res:=max(res,a[i,j]);
write(res);
end;
end;

begin
input;
init;
dp;
output;
end.


{$R-,Q-} uses math; const FINP=''; FOUT=''; MAXN=10000; oo=1000000000; var n:longint; a:array[1..MAXN,1..4] of longint; d:array[0..MAXN,0..15] of longint; procedure inp; var f:text; i:longint; begin assign(f,FINP); reset(f); read(f,n); for i:=1 to n do read(f,a[i,1]); for i:=1 to n do read(f,a[i,2]); for i:=1 to n do read(f,a[i,3]); for i:=1 to n do read(f,a[i,4]); close(f); end; procedure ans; var f:text; mask,kq:longint; begin assign(f,FOUT); rewrite(f); kq:=-oo; for mask:=0 to 15 do kq:=max(kq,d[n,mask]); writeln(f,kq); close(f); end; procedure refine; var i,j,kq:longint; f:text; begin for i:=1 to n do for j:=1 to 4 do if a[i,j]>0 then exit; kq:=-oo; assign(f,FOUT); rewrite(f); for i:=1 to n do for j:=1 to 4 do kq:=max(kq,a[i,j]); writeln(f,kq); close(f); halt; end; procedure solve; var mask,mask2,i,j,sum:longint; begin for i:=1 to n do for mask:=0 to 15 do if (mask and (mask shl 1)=0) and (mask and (mask shr 1)=0) then begin sum:=0; for j:=0 to 3 do if (mask shr j) and 1=1 then sum:=sum+a[i,j+1]; for mask2:=0 to 15 do if (mask2 and (mask2 shl 1)=0) and (mask2 and (mask2 shr 10)=0) then if mask and mask2=0 then d[i,mask]:=max(d[i,mask],d[i-1,mask2]+sum); end; end; begin inp; refine; solve; ans; end.  #### Code mẫu của hieult #include <stdio.h> //#include <conio.h> int main() { //freopen("QBSELECT.in","r",stdin); int f[10001][18],a[10001][6],n,max=-100000,KQ=0; scanf("%d",&n); for(int i = 1;i<=4;i++) for(int j = 1;j<=n;j++) { scanf("%d",&a[j][i]); if(max<a[j][i]) max = a[j][i]; } if(max <=0) printf("%d",max); else { for(int i = 0;i<=15;i++) f[0][i] = 0; int x[5],y[5],u,v,flag,maxx,tong; for(int i = 1;i<=n;i++) { for(int j = 0;j<=15;j++) { u=j; flag = 1; maxx = 0; tong = 0; for(int k = 1;k<=4;k++) { x[k] = u%2; u = u/2; if(k > 1 && x[k]*x[k-1]>0) { flag = 0; break; } if(x[k] == 1) tong = tong + a[i][k]; } if(flag ==0) f[i][j] = 0; else { for(int k = 0;k<=15;k++) { u = k; flag = 1; for(int l = 1;l<=4;l++) { y[l] = u%2; u = u/2; if((l > 1 && y[l]*y[l-1]>0)||(x[l]*y[l]>0)) { flag = 0; break; } } if(flag ==1 && f[i-1][k]>maxx) maxx = f[i-1][k]; } f[i][j] = tong + maxx; } } } for(int i = 0;i<=15;i++) { if(f[n][i]>KQ) KQ = f[n][i]; } printf("%d",KQ); } //getch(); }  #### Code mẫu của ll931110 {$MODE DELPHI}
Program QBSELECT;
Const
input  = '';
output = '';
Var
a: array[0..4,1..10000] of integer;
F: array[0..15,1..10000] of integer;
power: array[0..3] of integer;
stack: array[0..15,1..4] of integer;
n,max: integer;

Procedure init;
Var
fi: text;
i,j: integer;
Begin
Fillchar(a, sizeof(a), 0);

Assign(fi, input);
Reset(fi);

Readln(fi, n);
max:= -32000;

For i:= 1 to 4 do
For j:= 1 to n do
Begin
Read(fi, a[i,j]);
If max < a[i,j] then max:= a[i,j];
End;
Close(fi);
End;

Procedure pwr;
Var
i: integer;
Begin
power[0]:= 1;
For i:= 1 to 3 do power[i]:= power[i - 1] shl 1;
End;

Procedure adj;
Var
i,j,k: integer;
Begin
For i:= 0 to 15 do
If i and (i shl 1) = 0 then
Begin
j:= 0;
For k:= 0 to 3 do
if (i and power[k]) = power[k] then
Begin
inc(j);
stack[i,j]:= k + 1;
End;
End;
End;

Procedure optimize;
Var
i,j,k,s,tmp: integer;
Begin
Fillchar(F, sizeof(F), 0);

For i:= 0 to 15 do
For j:= 1 to 4 do F[i,1]:= F[i,1] + a[stack[i,j],1];

For k:= 2 to n do
For i:= 0 to 15 do if (i and (i shl 1) = 0) then
Begin
F[i,k]:= low(integer);
For j:= 0 to 15 do
if (i and j = 0) and (j and (j shl 1) = 0) then
Begin
tmp:= F[j,k - 1];
If F[i,k] < tmp then F[i,k]:= tmp;
End;
For s:= 1 to 4 do F[i,k]:= F[i,k] + a[stack[i,s],k];
End;
End;

Procedure solve;
Var
fo: text;
i,num: integer;
Begin
Assign(fo, output);
Rewrite(fo);

num:= 0;
For i:= 0 to 15 do if num < F[i,n] then num:= F[i,n];

If num = 0 then writeln(fo, max) else writeln(fo, num);
Close(fo);
End;

Begin
init;
pwr;
adj;
optimize;
solve;
End.


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

#include<stdio.h>
#include<vector>
#define MAX   10101
using namespace std;
int a[4][MAX];
int f[17][MAX];
vector<int> v[17];
int n;
int res;
const int INF=-2e9;
void init(void) {
int i,j;
scanf("%d",&n);
for (i=0;i<4;i=i+1)
for (j=1;j<=n;j=j+1)
scanf("%d",&a[i][j]);
}
bool fit(int s1,int s2) {
int i;
for (i=0;i<3;i=i+1) {
if (((s1|(1<<i))==s1) && ((s1|(1<<(i+1)))==s1)) return (false);
if (((s2|(1<<i))==s2) && ((s2|(1<<(i+1)))==s2)) return (false);
}
for (i=0;i<4;i=i+1)
if (((s1|(1<<i))==s1) && ((s2|(1<<i))==s2)) return (false);
return (true);
}
void gens(void) {
int i,j;
for (i=0;i<16;i=i+1)
for (j=0;j<16;j=j+1)
if (fit(i,j)) v[i].push_back(j);
}
void optimize(void) {
res=INF;
int i,j,k,l;
for (i=0;i<4;i=i+1)
for (j=1;j<=n;j=j+1)
if (a[i][j]>res) res=a[i][j];
if (res<=0) {
printf("%d",res);
return;
}
for (i=0;i<16;i=i+1)
for (j=1;j<=n;j=j+1)
f[i][j]=INF;
for (i=0;i<v[0].size();i=i+1){
f[v[0][i]][1]=0;
for (j=0;j<4;j=j+1)
f[v[0][i]][1]+=a[j][1]*((v[0][i]|(1<<j))==v[0][i]);
}
for (j=2;j<=n;j=j+1)
for (i=0;i<16;i=i+1) {
if (v[i].size()<1) continue;
for (k=0;k<v[i].size();k=k+1)
if (f[v[i][k]][j-1]>f[i][j]) f[i][j]=f[v[i][k]][j-1];
for (l=0;l<4;l=l+1)
f[i][j]+=a[l][j]*((i|(1<<l))==i);
}
res=INF;
for (i=0;i<16;i=i+1)
if ((n!=1) || (i!=0))
if (res<f[i][n]) res=f[i][n];
printf("%d",res);
}
int main(void) {
init();
gens();
optimize();
return 0;
}


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

#include <iostream>
using namespace std;

int n;
int a[4][10000];
int f[1<<4], g[1<<4];

int main() {
scanf("%d", &n);
for(int i=0;i<4;++i)
for(int j=0;j<n;++j)
scanf("%d", a[i]+j);
bool duong = false;
int mm = -1000000000;
for(int j=0;j<n;++j)
for(int i=0;i<4;++i) {
if(a[i][j]>0) duong = true;
else mm >?= a[i][j];
memset( g, 0, sizeof(g));
for(int bit=0;bit<(1<<4);++bit) {
if((bit&(1<<i))==0) {
g[bit] = f[bit];
g[bit] >?= f[bit|(1<<i)];
}
else {
if(i==0 || (bit&(1<<(i-1)))==0) {
int nb = (bit | (1<<i)) ^ (1<<i);
g[bit] >?= a[i][j] + f[nb];
}
}
}
memmove( f, g, sizeof(g));
}
if(!duong) cout << mm << endl;
else cout << *max_element( f, f+(1<<4)) << endl;
//system("pause");
return 0;
}


## Comments

Please read the guidelines before commenting.

There are no comments at the moment.