# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
523397 | boykut | UFO (IZhO14_ufo) | C++14 | 2084 ms | 8652 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>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>,
rb_tree_tag, tree_order_statistics_node_update> ordered_set;
vector<vector<int>> a;
vector<vector<long long>> pref;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m, r, k, p;
cin >> n >> m >> r >> k >> p;
a = vector<vector<int>>(n, vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> a[i][j];
}
}
while (k--) {
char c; cin >> c;
int x, y; cin >> x >> y;
int cnt = r;
x--;
if (c == 'W') {
auto getmax = [&](int l, int r) {
int ans = INT_MIN;
for (int j = l; j <= r; j++) ans = max(ans, a[x][j]);
return ans;
};
int start = 0;
while (cnt > 0 && start < m) {
int l = start, r = m - 1;
while (l < r) {
int m = (l + r) / 2;
if (getmax(start, m) >= y)
r = m;
else
l = m + 1;
}
if (a[x][r] >= y) {
a[x][r]--;
cnt--;
start = r + 1;
} else break;
}
} else if (c == 'E') {
for (int j = m - 1; j >= 0 && cnt > 0; j--) {
if (a[x][j] >= y) {
a[x][j]--;
cnt--;
}
}
} else if (c == 'N') {
for (int i = 0; i < n && cnt > 0; i++) {
if (a[i][x] >= y) {
a[i][x]--;
cnt--;
}
}
} else {
for (int i = n - 1; i >= 0 && cnt > 0; i--) {
if (a[i][x] >= y) {
a[i][x]--;
cnt--;
}
}
}
}
pref = vector<vector<long long>>(n, vector<long long>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
//cout << a[i][j] << ' ';
pref[i][j] = a[i][j];
pref[i][j] += (i ? pref[i-1][j] : 0);
pref[i][j] += (j ? pref[i][j-1] : 0);
pref[i][j] -= (i && j ? pref[i-1][j-1] : 0);
}
//cout << '\n';
}
auto get = [&](int a, int b, int c, int d) ->long long {
long long s = pref[c][d];
s -= (a ? pref[a-1][d] : 0);
s -= (b ? pref[c][b-1] : 0);
s += (a && b ? pref[a-1][b-1] : 0);
return s;
};
long long ans = LLONG_MIN;
for (int i = 0; i + p - 1 < n; i++) {
for (int j = 0; j + p - 1 < m; j++) {
ans = max(ans, get(i, j, i + p - 1, j + p - 1));
}
}
cout << ans << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |