| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 917418 |
2024-01-28T06:48:25 Z |
atom |
UFO (IZhO14_ufo) |
C++17 |
|
2000 ms |
27740 KB |
#include "bits/stdc++.h"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;
#ifdef JASPER
#include "debug.h"
#else
#define debug(...) 166
#endif
int n, m, rd, k, p;
vector <vector <int>> sh;
signed main() {
cin.tie(0) -> sync_with_stdio(0);
cin >> n >> m >> rd >> k >> p;
sh.assign(n + 5, vector <int> (m + 5, 0));
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
cin >> sh[i][j];
for (int _i = 1; _i <= k; ++_i) {
char cmd; int x, r, c, R, C, h;
cin >> cmd >> x >> h;
if (cmd == 'N') r = 1, c = x, R = n, C = x;
if (cmd == 'S') r = n, c = x, R = 1, C = x;
if (cmd == 'W') r = x, c = 1, R = x, C = m;
if (cmd == 'E') r = x, c = m, R = x, C = 1;
int cnt = rd;
if (cmd == 'N' || cmd == 'W') {
for (int i = r; i <= R; i++) {
for (int j = c; j <= C; ++j) {
if (sh[i][j] >= h && cnt > 0) {
sh[i][j]--;
cnt--;
}
}
}
}
else {
for (int i = r; i >= R; --i) {
for (int j = c; j >= C; --j) {
if (sh[i][j] >= h && cnt > 0) {
sh[i][j]--;
cnt--;
}
}
}
}
// debug(r, c, R, C, d, cnt);
}
// for (int i = 1; i <= n; ++i)
// for (int j = 1; j <= m; ++j)
// cout << sh[i][j] << " \n"[j == m];
vector <vector <ll>> prf(n + 5, vector <ll> (m + 5, 0));
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
prf[i][j] = prf[i - 1][j] + prf[i][j - 1] - prf[i - 1][j - 1] + sh[i][j];
auto qry = [&] (int x, int y, int X, int Y) {
return prf[X][Y] + prf[x - 1][y - 1] - prf[X][y - 1] - prf[x - 1][Y];
};
ll ans = 0;
for (int r = 1; r + p - 1 <= n; ++r) {
for (int c = 1; c + p - 1 <= m; ++c) {
int R = r + p - 1; int C = c + p - 1;
ll sum = qry(r, c, R, C);
if (ans < sum) {
// debug(r, c, R, C);
ans = sum;
}
}
}
cout << ans << "\n";
}
Compilation message
ufo.cpp: In function 'int main()':
ufo.cpp:24:32: warning: 'R' may be used uninitialized in this function [-Wmaybe-uninitialized]
24 | char cmd; int x, r, c, R, C, h;
| ^
ufo.cpp:33:22: warning: 'i' may be used uninitialized in this function [-Wmaybe-uninitialized]
33 | for (int i = r; i <= R; i++) {
| ^
ufo.cpp:24:26: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
24 | char cmd; int x, r, c, R, C, h;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
6 ms |
604 KB |
Output is correct |
| 5 |
Correct |
146 ms |
2012 KB |
Output is correct |
| 6 |
Correct |
165 ms |
9452 KB |
Output is correct |
| 7 |
Execution timed out |
2005 ms |
12608 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2015 ms |
9144 KB |
Time limit exceeded |
| 9 |
Execution timed out |
2051 ms |
7904 KB |
Time limit exceeded |
| 10 |
Execution timed out |
2050 ms |
8764 KB |
Time limit exceeded |
| 11 |
Execution timed out |
2044 ms |
8904 KB |
Time limit exceeded |
| 12 |
Execution timed out |
2055 ms |
8888 KB |
Time limit exceeded |
| 13 |
Execution timed out |
2007 ms |
12912 KB |
Time limit exceeded |
| 14 |
Execution timed out |
2056 ms |
8824 KB |
Time limit exceeded |
| 15 |
Execution timed out |
2017 ms |
9912 KB |
Time limit exceeded |
| 16 |
Execution timed out |
2058 ms |
9360 KB |
Time limit exceeded |
| 17 |
Execution timed out |
2035 ms |
16384 KB |
Time limit exceeded |
| 18 |
Execution timed out |
2060 ms |
12948 KB |
Time limit exceeded |
| 19 |
Execution timed out |
2047 ms |
10724 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2047 ms |
27740 KB |
Time limit exceeded |
