답안 #344734

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
344734 2021-01-06T11:38:23 Z _ani UFO (IZhO14_ufo) C++17
100 / 100
1940 ms 141180 KB
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
const int inf = 1'000'000'000;
vector<vector<ll>> a;
vector<vector<ll>> tr, tc;
void Buildr(int v, int vl, int vr, int i) {//checked
	if (vl == vr) {
		tr[i][v] = a[i][vl];
		return;
	}
	int m = (vl + vr) / 2;
	Buildr(v * 2, vl, m, i);
	Buildr(v * 2 + 1, m + 1, vr, i);
	tr[i][v] = max(tr[i][v * 2], tr[i][v * 2 + 1]);
}
void Buildc(int v, int vl, int vr, int j) {//checked
	if (vl == vr) {
		tc[j][v] = a[vl][j];
		return;
	}
	int m = (vl + vr) / 2;
	Buildc(v * 2, vl, m, j);
	Buildc(v * 2 + 1, m + 1, vr, j);
	tc[j][v] = max(tc[j][v * 2], tc[j][v * 2 + 1]);
}
int RFirstGreater(int v, int vl, int vr, int l, int r, int i, ll k) {//checked
	if (vl == vr) {
		if (tr[i][v] >= k)return vl;
		return inf;
	}
	if (vl == l && vr == r) {
		if (tr[i][v] < k)return inf;
		if (tr[i][v * 2] >= k)
			return RFirstGreater(v * 2, vl, (vl + vr) / 2, vl, (vl + vr) / 2, i, k);
		return RFirstGreater(v * 2 + 1, (vl + vr) / 2 + 1, vr, (vl + vr) / 2 + 1, vr, i, k);
	}
	int m = (vl + vr) / 2;
	if (r <= m)return RFirstGreater(v * 2, vl, m, l, r, i, k);
	if (l > m)return RFirstGreater(v * 2 + 1, m + 1, vr, l, r, i, k);
	
	int res = inf;
	res = min(res, RFirstGreater(v * 2, vl, m, l, min(r, m), i, k));
	res = min(res, RFirstGreater(v * 2 + 1, m + 1, vr, max(l, m + 1), r, i, k));
	return res;
}
int RLastGreater(int v, int vl, int vr, int l, int r, int i, ll k) {//checked
	if (vl == vr) {
		if (tr[i][v] >= k)return vl;
		return -1;
	}
	if (vl == l && vr == r) {
		if (tr[i][v] < k)return -1;
		if (tr[i][v * 2 + 1] >= k)
			return RLastGreater(v * 2 + 1, (vl + vr) / 2 + 1, vr, (vl + vr) / 2 + 1, vr, i, k);
		return RLastGreater(v * 2, vl, (vl + vr) / 2, vl, (vl + vr) / 2, i, k);
	}
	int m = (vl + vr) / 2;
	if (r <= m)return RLastGreater(v * 2, vl, m, l, r, i, k);
	if (l > m)return RLastGreater(v * 2 + 1, m + 1, vr, l, r, i, k);

	int res = -1;
	res = max(res, RLastGreater(v * 2, vl, m, l, min(r, m), i, k));
	res = max(res, RLastGreater(v * 2 + 1, m + 1, vr, max(l, m + 1), r, i, k));
	return res;
}
int CFirstGreater(int v, int vl, int vr, int l, int r, int j, ll k) {//checked
	if (vl == vr) {
		if (tc[j][v] >= k)return vl;
		return inf;
	}
	if (vl == l && vr == r) {
		if (tc[j][v] < k)return inf;
		if (tc[j][v * 2] >= k)
			return CFirstGreater(v * 2, vl, (vl + vr) / 2, vl, (vl + vr) / 2, j, k);
		return CFirstGreater(v * 2 + 1, (vl + vr) / 2 + 1, vr, (vl + vr) / 2 + 1, vr, j, k);
	}
	int m = (vl + vr) / 2;
	if (r <= m)return CFirstGreater(v * 2, vl, m, l, r, j, k);
	if (l > m)return CFirstGreater(v * 2 + 1, m + 1, vr, l, r, j, k);

	int res = inf;
	res = min(res, CFirstGreater(v * 2, vl, m, l, min(r, m), j, k));
	res = min(res, CFirstGreater(v * 2 + 1, m + 1, vr, max(l, m + 1), r, j, k));
	return res;
}
int CLastGreater(int v, int vl, int vr, int l, int r, int j, ll k) {//checked
	if (vl == vr) {
		if (tc[j][v] >= k)return vl;
		return -1;
	}
	if (vl == l && vr == r) {
		if (tc[j][v] < k)return -1;
		if (tc[j][v * 2 + 1] >= k)
			return CLastGreater(v * 2 + 1, (vl + vr) / 2 + 1, vr, (vl + vr) / 2 + 1, vr, j, k);
		return CLastGreater(v * 2, vl, (vl + vr) / 2, vl, (vl + vr) / 2, j, k);
	}
	int m = (vl + vr) / 2;
	if (r <= m)return CLastGreater(v * 2, vl, m, l, r, j, k);
	if (l > m)return CLastGreater(v * 2 + 1, m + 1, vr, l, r, j, k);

	int res = -1;
	res = max(res, CLastGreater(v * 2, vl, m, l, min(r, m), j, k));
	res = max(res, CLastGreater(v * 2 + 1, m + 1, vr, max(l, m + 1), r, j, k));
	return res;
}
void RUpd(int v, int vl, int vr, int i, int j) {//checked
	if (vl == vr) {
		tr[i][v]--;
		return;
	}
	int m = (vl + vr) / 2;
	if (j <= m)
		RUpd(v * 2, vl, m, i, j);
	else
		RUpd(v * 2 + 1, m + 1, vr, i, j);
	tr[i][v] = max(tr[i][v * 2], tr[i][v * 2 + 1]);
}
void CUpd(int v, int vl, int vr, int i, int j) {//checked
	if (vl == vr) {
		tc[j][v]--;
		return;
	}
	int m = (vl + vr) / 2;
	if (i <= m)
		CUpd(v * 2, vl, m, i, j);
	else
		CUpd(v * 2 + 1, m + 1, vr, i, j);
	tc[j][v] = max(tc[j][v * 2], tc[j][v * 2 + 1]);
}
ll Get(int v, int vl, int vr, int i, int j) {//checked
	if (vl == vr)return tr[i][v];
	int m = (vl + vr) / 2;
	if (j <= m)return Get(v * 2, vl, m, i, j);
	return Get(v * 2 + 1, m + 1, vr, i, j);
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n, m, r, k, p;
	cin >> n >> m >> r >> k >> p;
	a.resize(n);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
		{
			ll x;
			cin >> x;
			a[i].push_back(x);
		}
	tr.resize(n);
	for (int i = 0; i < n; i++) {
		tr[i].resize(4 * m + 4);
		Buildr(1, 0, m - 1, i);
	}
	tc.resize(m);
	for (int j = 0; j < m; j++) {
		tc[j].resize(4 * n + 4);
		Buildc(1, 0, n - 1, j);
	}
	while (k--)
	{
		char s;
		int x;
		ll h;
		cin >> s >> x >> h;
		x--;
		int ind;
		if (s == 'W' || s == 'N')ind = -1;
		else ind = inf;
		for (int i = 0; i < r; i++) {
			if (s == 'W') {
				int cur = RFirstGreater(1, 0, m - 1, ind + 1, m - 1, x, h);
			//	cerr << "cur index " << cur << '\n';
				if (cur == inf) break;
				RUpd(1, 0, m - 1, x, cur);
				CUpd(1, 0, n - 1, x, cur);
				ind = cur;
				if (ind + 1 >= m)
					break;
			}
			if (s == 'N') {
				int cur = CFirstGreater(1, 0, n - 1, ind + 1, n - 1, x, h);
			//	cerr << "cur index " << cur << '\n';
				if (cur == inf) break;
				RUpd(1, 0, m - 1, cur, x);
				CUpd(1, 0, n - 1, cur, x);
				ind = cur;
				if (ind + 1 >= n)
					break;
			}
			if (s == 'E') {
				int cur = RLastGreater(1, 0, m - 1, 0, min(ind, m) - 1, x, h);
			//	cerr << "cur index " << cur << '\n';
				if (cur == -1) break;
				RUpd(1, 0, m - 1, x, cur);
				CUpd(1, 0, n - 1, x, cur);
				ind = cur;
				if (ind - 1 < 0)
					break;
			}
			if (s == 'S') {
				int cur = CLastGreater(1, 0, n - 1, 0, min(ind, n) - 1, x, h);
			//	cerr << "cur index " << cur << '\n';
				if (cur == -1) break;
				RUpd(1, 0, m - 1, cur, x);
				CUpd(1, 0, n - 1, cur, x);
				ind = cur;
				if (ind - 1 < 0)
					break;
			}
		}
	}
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			a[i][j] = Get(1, 0, m - 1, i, j);
	ll ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
	//		cerr << a[i][j] << ' ';
			if (i + p > n || j + p > m)continue;
			ll cur = 0;
			for (int x = i; x < i + p; x++)
				for (int y = j; y < j + p; y++)
					cur += a[x][y];
			ans = max(ans, cur);
		}
	//	cerr << '\n';
	}
	cout << ans << '\n';
	return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 26 ms 1152 KB Output is correct
5 Correct 233 ms 4332 KB Output is correct
6 Correct 364 ms 36844 KB Output is correct
7 Correct 422 ms 77836 KB Output is correct
8 Correct 298 ms 78152 KB Output is correct
9 Correct 930 ms 74552 KB Output is correct
10 Correct 1259 ms 77956 KB Output is correct
11 Correct 869 ms 76640 KB Output is correct
12 Correct 1347 ms 78092 KB Output is correct
13 Correct 1518 ms 86528 KB Output is correct
14 Correct 1302 ms 76420 KB Output is correct
15 Correct 1389 ms 77964 KB Output is correct
16 Correct 356 ms 76696 KB Output is correct
17 Correct 1940 ms 86412 KB Output is correct
18 Correct 265 ms 73708 KB Output is correct
19 Correct 609 ms 84852 KB Output is correct
20 Correct 1516 ms 141180 KB Output is correct