| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 480094 | 1bin | 조개 줍기 (KOI17_shell) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 1505;
ll n, k, dp[NMAX][NMAX], a[NMAX][NMAX], base = 1, ans, x, y, l, r, p;
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;
}