Submission #464538

#	Time	Username	Problem	Language	Result	Execution time	Memory
464538		amunduzbaev	Game (eJOI20_game)	C++14	100 / 100	6 ms	972 KiB

game

#include "bits/stdc++.h"
using namespace std;

const int N = 25;
vector<int> edges[N*N], cycle, path;
int used[N*N], cntv, cnte;

map<array<int, 4>, int> mem;

//~ 0 cycle
//~ 1 path
//~      cycle, path, left for us, type

int rec(int i, int j, int left, int t){
	//~ cout<<i<<" "<<j<<" "<<left<<" "<<t<<"\n";
	if(i + 1 == (int)cycle.size() && j + 1 == (int)path.size()) return left;
	if(mem.count({i, j, left, t})) return mem[{i, j, left, t}];
	int& res = mem[{i, j, left, t}];
	res = -(1e9+7);
	
	if(t == 0 && left >= 4){
		res = max(res, left - 4 - rec(i, j, 4, -1));
	} if(t == 1 && left > 2){
		res = max(res, left - 2 - rec(i, j, 2, -1));
	}
	
	if(i + 1 < (int)cycle.size()){
		res = max(res, left - rec(i + 1, j, cycle[i + 1], 0));
	} if(j + 1 < (int)path.size()){
		res = max(res, left - rec(i, j + 1, path[j + 1], 1));
	}
	
	return res;
}

void dfs(int u){ used[u] = 1;
	cntv++;
	cnte += (int)edges[u].size();
	for(auto x : edges[u]){
		if(used[x]) continue;
		dfs(x);
	}
}

void solve(){
	int n, m; cin>>n>>m;
	vector<string> h(n+1), v(n);
	for(int i=0;i<n+1;i++) cin>>h[i];
	for(int i=0;i<n;i++) cin>>v[i];
	
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			int u = i * m + j;
			if(i && h[i][j] == '0') edges[u].push_back(u - m);
			if(i + 1 < n && h[i+1][j] == '0') edges[u].push_back(u + m);
			if(j && v[i][j] == '0') edges[u].push_back(u - 1);
			if(j + 1 < m && v[i][j+1] == '0') edges[u].push_back(u + 1);
			if(h[i][j] == '1' && h[i+1][j] == '1' && v[i][j] == '1' && v[i][j+1] == '1') used[i * m + j] = 1;
		}
	}
	
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			int u = i *	m + j;
			if(used[u]) continue;
			cnte = cntv = 0;
			dfs(u);
			if(cntv * 2 > cnte) path.push_back(cntv);
			else cycle.push_back(cntv);
		}
	}
	
	sort(path.begin(), path.end());
	sort(cycle.begin(), cycle.end());
	
	//~ for(auto x : path) cout<<x<<" ";
	//~ cout<<"\n";
	
	//~ for(auto x : cycle) cout<<x<<" ";
	//~ cout<<"\n";
	
	cout<<rec(-1, -1, 0, -1)<<"\n";
}

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t = 1;
	//~ cin>>t;
	while(t--) solve();
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20