| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 412198 |
2021-05-26T15:35:11 Z |
Theo830 |
Game (eJOI20_game) |
C++17 |
|
313 ms |
11892 KB |
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
ll INF = 1e9+7;
ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ii,ll>
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
///Stay Calm
///Look for special cases
///Beware of overflow and array bounds
///Think the problem backwards
///Training
ll n,m;
vll comp;
vector<ll>ch;
bool v[20][20];
char arr[21][20],ar[20][21];
bool in(ll x,ll y){
return (x < n && y < m) && min(x,y) >= 0;
}
typedef pair<set<ii>,ll> mr;
ll posa = 0,g = 1;
void dfs(ll x,ll y){
v[x][y] = 1;
posa++;
if(arr[x+1][y] == '0' && !in(x+1,y)){
g = 0;
}
else if(arr[x][y] == '0' && !in(x-1,y)){
g = 0;
}
else if(!in(x,y+1) && ar[x][y+1] == '0'){
g = 0;
}
else if(!in(x,y-1) && ar[x][y] == '0'){
g = 0;
}
if((in(x+1,y) && !v[x+1][y]) && arr[x+1][y] == '0'){
dfs(x+1,y);
}
if((in(x-1,y) && !v[x-1][y]) && arr[x][y] == '0'){
dfs(x-1,y);
}
if((in(x,y+1) && !v[x][y+1]) && ar[x][y+1] == '0'){
dfs(x,y+1);
}
if((in(x,y-1) && !v[x][y-1]) && ar[x][y] == '0'){
dfs(x,y-1);
}
}
map<mr,ll>mp;
map<mr,bool>ok;
ll diff = 0;
ll solve(ll p,set<ii>s){
if(s.empty()){
return 0;
}
if(ok[mr(s,p)]){
return mp[mr(s,p)];
}
ll ans;
if(p == 0){
ans = -INF;
set<ii>s2 = s;
for(auto f:s2){
ii x;
x.F = f.F;
x.S = f.S;
if(x.S == 2){
s.erase(x);
ans = max(ans,solve(p,s) + ch[x.F] + 1);
s.insert(x);
}
else if(x.S == 1){
s.erase(x);
x.S = 2;
s.insert(x);
ans = max(ans,solve(p,s) + comp[x.F] - (ch[x.F]+1));
s.erase(x);
x.S = 1;
s.insert(x);
}
else{
s.erase(x);
x.S = 1;
s.insert(x);
ans = max(ans,solve(p^1,s));
s.erase(x);
x.S = 0;
s.insert(x);
}
}
}
else{
ans = INF;
set<ii>s2 = s;
for(auto f:s2){
ii x;
x.F = f.F;
x.S = f.S;
if(x.S == 2){
s.erase(x);
ans = min(ans,solve(p,s) - ch[x.F] - 1);
s.insert(x);
}
else if(x.S == 1){
s.erase(x);
x.S = 2;
s.insert(x);
ans = min(ans,solve(p,s) - comp[x.F] + ch[x.F] + 1);
s.erase(x);
x.S = 1;
s.insert(x);
}
else{
s.erase(x);
x.S = 1;
s.insert(x);
ans = min(ans,solve(p^1,s));
s.erase(x);
x.S = 0;
s.insert(x);
}
}
}
ok[mr(s,p)] = 1;
mp[mr(s,p)] = ans;
return ans;
}
int main(void){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
f(i,0,n+1){
f(j,0,m){
cin>>arr[i][j];
}
}
f(i,0,n){
f(j,0,m+1){
cin>>ar[i][j];
}
}
ll ans = -INF;
memset(v,0,sizeof v);
f(i,0,n){
f(j,0,m){
if(!v[i][j]){
posa = 0;
g = 1;
dfs(i,j);
if(posa != 1 || (arr[i][j] == '0' || arr[i+1][j] == '0' || ar[i][j] == '0' || ar[i][j+1] == '0')){
comp.pb(posa);
ch.pb(g);
}
}
}
}
set<ii>e;
ll pos = 0;
for(auto x:comp){
e.insert(ii(pos,0LL));
assert(ch[pos]+1 <= comp[pos]);
pos++;
}
cout<<solve(0,e);
}
/*
3 3
000
111
011
110
1010
1000
1001
5 5
00100
10100
11010
00100
01000
11100
011111
001011
101011
110111
100111
*/
Compilation message
game.cpp: In function 'int main()':
game.cpp:174:14: warning: unused variable 'x' [-Wunused-variable]
174 | for(auto x:comp){
| ^
game.cpp:157:8: warning: unused variable 'ans' [-Wunused-variable]
157 | ll ans = -INF;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
316 KB |
Output is correct |
| 7 |
Correct |
2 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
316 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
313 ms |
11892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
316 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
316 KB |
Output is correct |
| 11 |
Correct |
2 ms |
204 KB |
Output is correct |
| 12 |
Correct |
1 ms |
204 KB |
Output is correct |
| 13 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
