제출 #1134428

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1134428		stdfloat	UFO (IZhO14_ufo)	C++20	95 / 100	2098 ms	145232 KiB

ufo

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

using ll = long long;

#define sz(v)	(int)(v).size()
#define all(v)	(v).begin(), (v).end()

vector<vector<int>> st[4];

int upd(int tp, int x, int nd, int l, int r, int y, int vl) {
	if (r < y || y < l) return st[tp][x][nd];

	if (l == r) return st[tp][x][nd] += vl;

	int ch = (nd << 1) | 1, md = (l + r) >> 1;
	return st[tp][x][nd] = max(upd(tp, x, ch, l, md, y, vl), upd(tp, x, ch + 1, md + 1, r, y, vl));
}

int fnd(int tp, int x, int nd, int l, int r, int ind, int vl) {
	if (r <= ind || st[tp][x][nd] < vl) return -1;

	if (l == r) return l;

	int ch = (nd << 1) | 1, md = (l + r) >> 1;

	int res = fnd(tp, x, ch, l, md, ind, vl);
	if (!~res) res = fnd(tp, x, ch + 1, md + 1, r, ind, vl);

	return res;
}

int fnd2(int tp, int x, int nd, int l, int r, int y) {
	if (r < y || y < l) return 0;

	if (l == r) return st[tp][x][nd];

	int ch = (nd << 1) | 1, md = (l + r) >> 1;
	return max(fnd2(tp, x, ch, l, md, y), fnd2(tp, x, ch + 1, md + 1, r, y));
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);

	int n, m, R, K, P;
	cin >> n >> m >> R >> K >> P;

	vector<vector<int>> a(n, vector<int>(m));
	for (auto &i : a) {
		for (auto &j : i)
			cin >> j;
	}

	for (int i = 0; i < 4; i++)
		st[i].assign((i < 2 ? n : m), vector<int>((i < 2 ? m : n) << 2));

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			upd(0, i, 0, 0, m - 1, j, a[i][j]);
			upd(1, i, 0, 0, m - 1, m - j - 1, a[i][j]);
			upd(2, j, 0, 0, n - 1, i, a[i][j]);
			upd(3, j, 0, 0, n - 1, n - i - 1, a[i][j]);
		}
	}

	while (K--) {
		char c;
		int x, h;
		cin >> c >> x >> h; x--;

		int tp = (c == 'W' ? 0 : c == 'E' ? 1 : 2 + (c == 'S')), r = (tp < 2 ? m : n) - 1, ind = -1;
		for (int z = 0; z < R; z++) {
			ind = fnd(tp, x, 0, 0, r, ind, h);

			if (ind == -1) break;

			int remx = x, remind = ind;

			if (tp & 1) ind = r - ind;
			if (1 < tp) swap(x, ind);

			upd(0, x, 0, 0, m - 1, ind, -1);
			upd(1, x, 0, 0, m - 1, m - ind - 1, -1);
			upd(2, ind, 0, 0, n - 1, x, -1);
			upd(3, ind, 0, 0, n - 1, n - x - 1, -1);
		
			x = remx; ind = remind;
		}

	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++)
			a[i][j] = fnd2(0, i, 0, 0, m - 1, j);
	}

	ll mx = 0;
	for (int i = 0; i + P <= n; i++) {
		for (int j = 0; j + P <= m; j++) {
			ll sm = 0;
			for (int x = i; x < i + P; x++) {
				for (int y = j; y < j + P; y++)
					sm += a[x][y];
			}

			mx = max(mx, sm);
		}
	}

	cout << mx;
}

• Subtask 1: 95 / 100