Submission #467068

#	Time	Username	Problem	Language	Result	Execution time	Memory
467068		Stickfish	T-Covering (eJOI19_covering)	C++17	0 / 100	4 ms	460 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(int i0, int j0, int i1, int j1){
	int ans = 0;
	for(int i = i0; i <= i1; ++i){
		for(int j = j0; j <= j1; ++j){
			ans += fill(i, j);
		}
	}
	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];
	}
	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(i, j - 1, i + 1, j + 1);
				ans += fill(i - 1, j);
				ans += fill(i + 2, j);
				special[i][j] = 0;
				special[i + 1][j] = 0;
			}
			if(special[i][j + 1]){
				ans += fill(i - 1, j, i + 1, j + 1);
				ans += fill(i, j - 1);
				ans += fill(i, j + 2);
				special[i][j] = 0;
				special[i][j + 1] = 0;
			}
			if(special[i + 1][j + 1]){
				ans += fill(i, j, i + 1, j + 1);
				ans += fill(i, j - 1);
				ans += fill(i - 1, j);
				ans += fill(i + 1, j + 2);
				ans += fill(i + 2, j + 1);
				special[i][j] = 0;
				special[i + 1][j + 1] = 0;
			}
			if(special[i - 1][j + 1]){
				ans += fill(i - 1, j, i, j + 1);
				ans += fill(i, j - 1);
				ans += fill(i + 1, j);
				ans += fill(i, j - 1);
				ans += fill(i - 1, j + 2);
				ans += fill(i - 2, j + 1);
				special[i][j] = 0;
				special[i - 1][j + 1] = 0;
			}
		}
	}
	//cout << ans << endl;
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= m; ++j){
			if(special[i][j]){
				ans += fill(i - 1, j, i + 1, j);
				ans += fill(i, j + 1);
				ans += fill(i, j - 1);
				complex<int> cmpl = 1;
				for(complex<int> timer = 0, mv = 1; timer != 4; timer += 1, mv *= IMAG){
					if(used[i + mv.real()][j + mv.imag()]){
						cmpl = mv;
						break;
					}
					if(f[i + mv.real()][j + mv.imag()] < f[i + cmpl.real()][j + cmpl.imag()]){
						cmpl = mv;
					}
				}
				ans -= unfill(i + cmpl.real(), j + cmpl.imag());
			}
		}
	}
	//return 0;
	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;
}

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