Submission #432709
Source Code Expand
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<string>
#include<stack>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<int,P> P1;
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define rep(i,x) for(int i=0;i<x;i++)
#define rep1(i,x) for(int i=1;i<=x;i++)
#define rrep(i,x) for(int i=x-1;i>=0;i--)
#define rrep1(i,x) for(int i=x;i>0;i--)
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
#define mp1(a,b,c) P1(a,P(b,c))
const int INF=1000000000;
const int dir_4[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
const int dir_8[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};
int a[3][3],b[2][3],c[3][2];
int dfs(int k){
if(k == 9){
int ret = 0;
rep(i,2)rep(j,3)if(a[i][j] == a[i+1][j])ret += b[i][j];
rep(i,3)rep(j,2)if(a[i][j] == a[i][j+1])ret += c[i][j];
return ret;
}
if(k%2 == 0){
int ret = 0;
rep(i,3){
rep(j,3){
if(a[i][j] == -1){
a[i][j] = 0;
ret = max ( ret , dfs(k+1) );
a[i][j] = -1;
}
}
}
return ret;
}
else {
int ret = INF;
rep(i,3){
rep(j,3){
if(a[i][j] == -1){
a[i][j] = 1;
ret = min ( ret , dfs(k+1) );
a[i][j] = -1;
}
}
}
return ret;
}
}
int main(){
int sum = 0;
rep(i,2)rep(j,3){ cin >> b[i][j]; sum += b[i][j]; }
rep(i,3)rep(j,2){ cin >> c[i][j]; sum += c[i][j]; }
rep(i,3)rep(j,3)a[i][j] = -1;
int ans = dfs(0);
printf("%d\n%d\n",ans,sum-ans);
}
Submission Info
Submission Time |
|
Task |
C - 双子と○×ゲーム |
User |
yokozuna57 |
Language |
C++11 (GCC 4.9.2) |
Score |
100 |
Code Size |
1836 Byte |
Status |
AC |
Exec Time |
91 ms |
Memory |
1052 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
100 / 100 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample-01.txt, sample-02.txt |
All |
test-01.txt, test-02.txt, test-03.txt, test-04.txt, test-05.txt, test-06.txt, test-07.txt, test-08.txt, test-09.txt, test-10.txt, test-11.txt, test-12.txt, test-13.txt, test-14.txt, test-15.txt, test-16.txt, test-17.txt, test-18.txt, test-19.txt, test-20.txt, sample-01.txt, sample-02.txt |
Case Name |
Status |
Exec Time |
Memory |
sample-01.txt |
AC |
70 ms |
1048 KB |
sample-02.txt |
AC |
70 ms |
948 KB |
test-01.txt |
AC |
70 ms |
1052 KB |
test-02.txt |
AC |
91 ms |
960 KB |
test-03.txt |
AC |
71 ms |
864 KB |
test-04.txt |
AC |
70 ms |
940 KB |
test-05.txt |
AC |
70 ms |
1040 KB |
test-06.txt |
AC |
71 ms |
940 KB |
test-07.txt |
AC |
70 ms |
1044 KB |
test-08.txt |
AC |
71 ms |
1036 KB |
test-09.txt |
AC |
70 ms |
912 KB |
test-10.txt |
AC |
70 ms |
916 KB |
test-11.txt |
AC |
70 ms |
912 KB |
test-12.txt |
AC |
70 ms |
1040 KB |
test-13.txt |
AC |
71 ms |
916 KB |
test-14.txt |
AC |
71 ms |
944 KB |
test-15.txt |
AC |
69 ms |
944 KB |
test-16.txt |
AC |
71 ms |
1048 KB |
test-17.txt |
AC |
70 ms |
936 KB |
test-18.txt |
AC |
74 ms |
940 KB |
test-19.txt |
AC |
73 ms |
944 KB |
test-20.txt |
AC |
75 ms |
856 KB |