Submission #467237

#	Time	Username	Problem	Language	Result	Execution time	Memory
467237		Stickfish	T-Covering (eJOI19_covering)	C++17	55 / 100	261 ms	13348 KiB

covering

#include <iostream>
#include <vector>
#include <complex>
using namespace std;
using ll = long long;

const complex<int> IMAG(0, 1);
vector<vector<int>> special;
vector<vector<int>> used;
vector<vector<int>> f;

int unfill(int i, int j){
	--used[i][j];
	return -f[i][j];
}

int fill(int i, int j){
	++used[i][j];
	return f[i][j];
}

int fill_plus(int i, int j){
	int ans = fill(i, j);
	for(complex<int> timer = 0, mv = 1; timer != 4; timer += 1, mv *= IMAG){
		ans += fill(i + mv.real(), j + mv.imag());
	}
	special[i][j] = 0;
	return ans;
}

int dfs(int i, int j){
	if(special[i][j]){
		int ans = 0;
		for(complex<int> timer = 0, mv = 1; timer != 4; timer += 1, mv *= IMAG){
			if(used[i + mv.real()][j + mv.imag()]){
				ans += unfill(i + mv.real(), j + mv.imag());
				break;
			}
		}
		ans += fill_plus(i, j);
		for(complex<int> timer = 0, mv = 1; timer != 4; timer += 1, mv *= IMAG){
			ans += dfs(i + mv.real(), j + mv.imag());
		}
		return ans;
	} else {
		for(complex<int> timer = 0, mv = 1; timer != 4; timer += 1, mv *= IMAG){
			if(0 < i + mv.real() && i + mv.real() < f.size() && 0 < j + mv.imag() && j + mv.imag() < f[0].size() && special[i + mv.real()][j + mv.imag()]){
				return dfs(i + mv.real(), j + mv.imag());
			}
		}
		return 0;
	}
}

complex<int> mindfs(int i, int j){
	complex<int> ans = i + 1 + j * IMAG;
	for(complex<int> timer = 0, mv = 1; timer != 4; timer += 1, mv *= IMAG){
		if(f[ans.real()][ans.imag()] > f[i + mv.real()][j + mv.imag()]){
			ans = mv + i + j * IMAG;
		}
	}
	special[i][j] = 2;
	for(complex<int> timer = 0, mv = 1; timer != 4; timer += 1, mv *= IMAG){
		if(special[i + mv.real() * 2][j + mv.imag() * 2] == 1){
			complex<int> nans = mindfs(i + mv.real() * 2, j + mv.imag() * 2);
			if(f[ans.real()][ans.imag()] > f[nans.real()][nans.imag()]){
				ans = nans;
			}
		}
	}
	return ans;
}

signed main(){
	int n, m;
	cin >> n >> m;
	f.assign(n + 2, vector<int>(m + 2));
	used.assign(n + 2, vector<int>(m + 2));
	special.assign(n + 2, vector<int>(m + 2));
	for(int i = 0; i <= n + 1; ++i)
		used[i][0] = used[i][m + 1] = 1;
	for(int j = 0; j <= m + 1; ++j)
		used[0][j] = used[n + 1][j] = 1;
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= m; ++j){
			cin >> f[i][j];
		}
	}
	
	int q;
	cin >> q;
	for(int i = 0; i < q; ++i){
		int x, y;
		cin >> x >> y;
		++x, ++y;
		special[x][y] = 1;
	}
	ll ans = 0;
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= m; ++j){
			if(!special[i][j])
				continue;
			if(special[i + 1][j]){
				ans += fill_plus(i, j);
				ans += unfill(i + 1, j);
				ans += fill_plus(i + 1, j);
				ans += unfill(i, j);
			}
			if(special[i][j + 1]){
				ans += fill_plus(i, j);
				ans += unfill(i, j + 1);
				ans += fill_plus(i, j + 1);
				ans += unfill(i, j);
			}
			if(special[i + 1][j + 1]){
				ans += fill_plus(i, j);
				ans += unfill(i, j + 1);
				ans += fill_plus(i + 1, j + 1);
				ans += unfill(i + 1, j);
			}
			if(special[i - 1][j + 1]){
				ans += fill_plus(i, j);
				ans += unfill(i, j + 1);
				ans += fill_plus(i - 1, j + 1);
				ans += unfill(i - 1, j);
			}
		}
	}

	for(int i = 0; i <= n + 1; ++i){
		for(int j = 0; j <= m + 1; ++j){
			if(used[i][j]){
				ans += dfs(i, j);
			}
		}
	}

	//for(int i = 0; i <= n + 1; ++i){
		//for(int j = 0; j <= m + 1; ++j){
			//cout << used[i][j] << ' ';
		//}
		//cout << endl;
	//}
	//cout << ans << endl;

	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= m; ++j){
			if(special[i][j]){
				complex<int> pt = mindfs(i, j);
				used[pt.real()][pt.imag()] = 1;
				ans += dfs(pt.real(), pt.imag());
			}
		}
	}

	for(int i = 0; i <= n + 1; ++i){
		for(int j = 0; j <= m + 1; ++j){
			if(used[i][j] > 1){
				cout << "No\n";
				return 0;
			}
		}
	}
	cout << ans << endl;
}

Compilation message (stderr)

covering.cpp: In function 'int dfs(int, int)':
covering.cpp:47:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |    if(0 < i + mv.real() && i + mv.real() < f.size() && 0 < j + mv.imag() && j + mv.imag() < f[0].size() && special[i + mv.real()][j + mv.imag()]){
      |                            ~~~~~~~~~~~~~~^~~~~~~~~~
covering.cpp:47:91: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |    if(0 < i + mv.real() && i + mv.real() < f.size() && 0 < j + mv.imag() && j + mv.imag() < f[0].size() && special[i + mv.real()][j + mv.imag()]){
      |                                                                             ~~~~~~~~~~~~~~^~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 15
• Subtask 6: 20 / 20
• Subtask 7: 0 / 30