Submission #480096

#	Time	Username	Problem	Language	Result	Execution time	Memory
480096		1bin	조개 줍기 (KOI17_shell)	C++14	100 / 100	1525 ms	92572 KiB

shell

#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 1505;
int n, k, base = 1, x, y, l, r;
ll  dp[NMAX][NMAX], a[NMAX][NMAX], p ,ans;
vector<ll> seg[NMAX];
char c;

void update(int y, int idx, ll v) {
	idx += base;
	while (idx) {
		seg[y][idx] += v;
		idx /= 2;
	}
	return;
}

ll find(int y, int l, int r) {
	ll ret = dp[y][r];
	l += base; r += base;
	while (l <= r) {
		if (l & 1) ret += seg[y][l++];
		if (!(r & 1)) ret += seg[y][r--];
		l /= 2; r /= 2;
	}
	return ret;
}

int main(void) {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> n;
	while (base < n + 2) base *= 2;
	for (int i = 0; i <= n; i++) seg[i].resize(base * 2);

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) cin >> a[i][j];
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {
			dp[i][j] = max(dp[i][j], dp[i - 1][j]);
			dp[i][j] = max(dp[i][j], dp[i][j - 1]);
			dp[i][j] += a[i][j];
			ans += dp[i][j];
		}

	cout << ans << '\n';
	for (int t = 0; t < n; t++) {
		cin >> c >> y >> x;
		l = r = x;
		(c == 'U') ? p = 1 : p = -1;
		a[y][x] += p;
		for (int i = y; i <= n; i++) {
			if (i != y) {
				for (; l <= r; l++) {
					ll b = find(i, 0, l);
					ll now = max(find(i, 0, l - 1), find(i - 1, 0, l)) + a[i][l];
					if (b != now) break;
				}
			}
			if (l > r) break;
			update(i, l, p);
			for (; r + 1 <= n; r++) {
				ll b = find(i, 0, r + 1) - p;
				ll now = max(find(i, 0, r), find(i - 1, 0, r + 1)) + a[i][r + 1];
				if (now == b) break;
			}
			update(i, r + 1, -p);
			//cout << "L : " << l << "   R : " << r << '\n';
			ans += p * (r - l + 1);
		}
		cout << ans << '\n';
	}
	return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 34 / 34
• Subtask 3: 54 / 54