oj.uz

답안 #344704

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
344704 2021-01-06T09:44:27 Z _ani UFO (IZhO14_ufo) C++17
25 / 100
 2000 ms 141264 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 i, ll k) {//checked
	if (vl == vr) {
		if (tr[i][v] >= k)return vl;
		return inf;
	}
	int m = (vl + vr) / 2;
	if (l > m)return RFirstGreater(v * 2 + 1, m + 1, vr, l, i, k);
	int res = inf;
	if (tr[i][v * 2 + 1] >= k)
		res = min(res, RFirstGreater(v * 2 + 1, m + 1, vr, l, i, k));
	res = min(res, RFirstGreater(v * 2, vl, m, l, i, k));
	return res;
}
int RLastGreater(int v, int vl, int vr, int r, int i, ll k) {//checked
	if (vl == vr) {
		if (tr[i][v] >= k)return vl;
		return -1;
	}
	int m = (vl + vr) / 2;
	if (r <= m)
		return RLastGreater(v * 2, vl, m, r, i, k);
	///
	int res = -1;
	if (tr[i][v * 2 + 1] >= k)
		res = max(res, RLastGreater(v * 2 + 1, m + 1, vr, r, i, k));
	res = max(res, RLastGreater(v * 2, vl, m, r, i, k));
	return res;
}
int CFirstGreater(int v, int vl, int vr, int l, int j, ll k) {//checked
	if (vl == vr) {
		if (tc[j][v] >= k)return vl;
		return inf;
	}
	int m = (vl + vr) / 2;
	if (l > m)return CFirstGreater(v * 2 + 1, m + 1, vr, l, j, k);
	int res = inf;
	if (tc[j][v * 2 + 1] >= k)
		res = min(res, CFirstGreater(v * 2 + 1, m + 1, vr, l, j, k));
	res = min(res, CFirstGreater(v * 2, vl, m, l, j, k));
	return res;
}
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 CLastGreater(int v, int vl, int vr, int r, int j, ll k) {//checked
	if (vl == vr) {
		if (tc[j][v] >= k)return vl;
		return -1;
	}
	int m = (vl + vr) / 2;
	int res = -1;
	if (r <= m)return CLastGreater(v * 2, vl, m, r, j, k);
	if (tc[j][v * 2 + 1] >= k)
		res = max(res, CLastGreater(v * 2 + 1, m + 1, vr, r, j, k));
	res = max(res, CLastGreater(v * 2, vl, m, 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]);
}
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, 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, 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, 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, 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, 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;
}

Subtask #1
25.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 3 ms 492 KB Output is correct
4 Correct 83 ms 1140 KB Output is correct
5 Execution timed out 2060 ms 4332 KB Time limit exceeded
6 Execution timed out 2035 ms 36716 KB Time limit exceeded
7 Execution timed out 2032 ms 78120 KB Time limit exceeded
8 Execution timed out 2095 ms 77956 KB Time limit exceeded
9 Execution timed out 2098 ms 74424 KB Time limit exceeded
10 Execution timed out 2089 ms 77980 KB Time limit exceeded
11 Execution timed out 2100 ms 76548 KB Time limit exceeded
12 Execution timed out 2099 ms 77836 KB Time limit exceeded
13 Execution timed out 2080 ms 86508 KB Time limit exceeded
14 Execution timed out 2086 ms 76420 KB Time limit exceeded
15 Execution timed out 2062 ms 78192 KB Time limit exceeded
16 Execution timed out 2059 ms 76548 KB Time limit exceeded
17 Execution timed out 2102 ms 86528 KB Time limit exceeded
18 Correct 1591 ms 73708 KB Output is correct
19 Execution timed out 2052 ms 84856 KB Time limit exceeded
20 Execution timed out 2091 ms 141264 KB Time limit exceeded