Seletiva IOI 2013

domino.cpp

// Ivan Carvalho
// Dominó - Seletiva IOI - OBI 2013
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e4 + 10;
int m[MAXN][3];
int dp[MAXN][2][2][2];
int N;
int solve(int pos,int a1,int a2,int a3){
	if(pos > N + 1) return 0;
	if(dp[pos][a1][a2][a3] != -1) return dp[pos][a1][a2][a3];
	int ret = max(m[pos][0]*m[pos][1] + solve(pos+1,0,0,1),m[pos][1]*m[pos][2] + solve(pos+1,1,0,0));
	ret = max(ret,solve(pos+1,1,1,1));
	if(a1 == 1){
		ret = max(ret, solve(pos+1,0,0,0) + m[pos-1][0]*m[pos][0] + m[pos][1]*m[pos][2]);
		ret = max(ret, solve(pos+1,0,1,1) + m[pos-1][0]*m[pos][0]);
	}
	if(a2 == 1){
		ret = max(ret, solve(pos+1,1,0,1) + m[pos-1][1]*m[pos][1] );
	}
	if(a3 == 1){
		ret = max(ret, solve(pos+1,0,0,0) + m[pos-1][2]*m[pos][2] + m[pos][0]*m[pos][1]);
		ret = max(ret, solve(pos+1,1,1,0) + m[pos-1][2]*m[pos][2]);
	}
	if(a1 == 1 && a2 == 1){
		ret = max(ret, solve(pos+1,1,1,1) + m[pos-1][0]*m[pos-1][1] );
		ret = max(ret, solve(pos+1,0,0,1) + m[pos-1][0]*m[pos-1][1] + m[pos][0]*m[pos][1]);
		ret = max(ret, solve(pos+1,0,0,1) + m[pos-1][0]*m[pos][0] + m[pos-1][1]*m[pos][1]);
		ret = max(ret, solve(pos+1,1,0,0) + m[pos-1][0]*m[pos-1][1] + m[pos][1]*m[pos][2]);
	}
	if(a1 == 1 && a3 == 1){
		ret = max(ret, solve(pos+1,0,1,0) + m[pos-1][0]*m[pos][0] + m[pos-1][2]*m[pos][2]);
	}
	if(a2 == 1 && a3 == 1){
		ret = max(ret,solve(pos+1,1,1,1) + m[pos-1][1]*m[pos-1][2]);
		ret = max(ret,solve(pos+1,1,0,0) + m[pos-1][1]*m[pos-1][2] + m[pos][1]*m[pos][2]);
		ret = max(ret,solve(pos+1,1,0,0) + m[pos-1][1]*m[pos][1] + m[pos-1][2]*m[pos][2]);
		ret = max(ret,solve(pos+1,0,0,1) + m[pos-1][1]*m[pos-1][2] + m[pos][0]*m[pos][1]);
	}
	if(a1 == 1 && a2 == 1 && a3 == 1){
		ret = max(ret, solve(pos+1,1,1,1) + m[pos-1][0]*m[pos-1][1] );
		ret = max(ret,solve(pos+1,1,1,1) + m[pos-1][1]*m[pos-1][2]);
		ret = max(ret,solve(pos+1,0,0,0) + m[pos-1][0]*m[pos][0] + m[pos-1][1]*m[pos][1] + m[pos-1][2]*m[pos][2] );
		ret = max(ret, solve(pos+1,0,0,0) + m[pos-1][0]*m[pos-1][1] + m[pos][0]*m[pos][1] + m[pos-1][2]*m[pos][2]);
		ret = max(ret, solve(pos+1,0,0,0) + m[pos-1][0]*m[pos][0] + m[pos-1][1]*m[pos-1][2] + m[pos][1]*m[pos][2]);
		ret = max(ret, solve(pos+1,1,0,0) + m[pos][1]*m[pos][2] + m[pos-1][0]*m[pos-1][1]);
		ret = max(ret, solve(pos+1,0,0,1) + m[pos-1][1]*m[pos-1][2] + m[pos][0]*m[pos][1] );
	}
	return dp[pos][a1][a2][a3] = ret;
}
int main(){
	scanf("%d",&N);
	for(int i = 1;i<=N;i++) scanf("%d",&m[i][0]);
	for(int i = 1;i<=N;i++) scanf("%d",&m[i][1]);
	for(int i = 1;i<=N;i++) scanf("%d",&m[i][2]);
	memset(dp,-1,sizeof(dp));
	printf("%d\n",solve(1,0,0,0));
	return 0;
}