| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 334253 |
2020-12-08T18:51:04 Z |
Pety |
UFO (IZhO14_ufo) |
C++14 |
|
2000 ms |
137452 KB |
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
using namespace std;
int n, m, k, r, p;
vector<vector<int>>aint_lin, aint_col, a;
vector<vector<long long>>sum;
void init () {
aint_lin.resize(n + 2);
aint_col.resize(m + 2);
a.resize(n+2);
sum.resize(n+2);
for (int i = 0; i <= n + 1; i++) {
a[i].resize(m + 2);
sum[i].resize(m + 2);
aint_lin[i].resize(4 * m + 2);
}
for (int i = 0; i <= m + 1; i++)
aint_col[i].resize(4 * n + 2);
}
int mid;
void updateLin (int poz, int nod, int st, int dr, int pozhatz, int val) {
if (st == dr) {
aint_lin[poz][nod] = val;
return;
}
mid = (st + dr) / 2;
if (pozhatz <= mid)
updateLin(poz, 2 * nod, st, mid, pozhatz, val);
else
updateLin(poz, 2 * nod + 1, mid + 1, dr, pozhatz, val);
aint_lin[poz][nod] = max(aint_lin[poz][2 * nod], aint_lin[poz][2 * nod + 1]);
}
void updateCol (int poz, int nod, int st, int dr, int pozhatz, int val) {
if (st == dr) {
aint_col[poz][nod] = val;
return;
}
mid = (st + dr) / 2;
if (pozhatz <= mid)
updateCol(poz, 2 * nod, st, mid, pozhatz, val);
else
updateCol(poz, 2 * nod + 1, mid + 1, dr, pozhatz, val);
aint_col[poz][nod] = max(aint_col[poz][2 * nod], aint_col[poz][2 * nod + 1]);
}
int queryLin (bool ok, int nod, int st, int dr, int poz, int lvl) {
if (st == dr)
return st;
mid = (st + dr) / 2;
if (!ok) {
if (aint_lin[poz][2 * nod] >= lvl)
return queryLin(ok, 2* nod, st, mid, poz, lvl);
else
return queryLin(ok, 2 * nod + 1, mid + 1, dr, poz, lvl);
}
else {
if (aint_lin[poz][2 * nod + 1] >= lvl)
return queryLin(ok, 2* nod + 1, mid + 1, dr, poz, lvl);
else
return queryLin(ok, 2 * nod, st, mid, poz, lvl);
}
}
int queryCol (bool ok, int nod, int st, int dr, int poz, int lvl) {
if (st == dr)
return st;
mid = (st + dr) / 2;
if (!ok) {
if (aint_col[poz][2 * nod] >= lvl)
return queryCol(ok, 2* nod, st, mid, poz, lvl);
else
return queryCol(ok, 2 * nod + 1, mid + 1, dr, poz, lvl);
}
else {
if (aint_col[poz][2 * nod + 1] >= lvl)
return queryCol(ok, 2* nod + 1, mid + 1, dr, poz, lvl);
else
return queryCol(ok, 2 * nod, st, mid, poz, lvl);
}
}
void Laserlin (int dr, bool ok, int poz, int lvl) {
int r1 = r;
int x;
int last = 0;
vector<int > kasa;
while (r1) {
x = queryLin(ok, 1, 1 , dr, poz, lvl);
a[poz][x]--;
kasa.push_back(x);
last = x;
updateLin(poz, 1, 1, m, x, 0);
r1--;
}
for (auto it : kasa) {
updateLin(poz, 1, 1, m, it, a[poz][it]);
updateCol(it, 1, 1, n, poz, a[poz][it]);
}
}
void Lasercol (int dr, bool ok, int poz, int lvl) {
int r1 = r;
int last = 0;
int x;
vector<int > kasa;
while (r1) {
x = queryCol(ok, 1, 1, dr, poz, lvl);
a[x][poz]--;
kasa.push_back(x);
last = x;
updateCol(poz, 1, 1, n, x, 0);
r1--;
}
for (auto it : kasa) {
updateLin(it, 1, 1, m, poz, a[it][poz]);
updateCol(poz, 1, 1, n, it, a[it][poz]);
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> m >> r >> k >> p;
init();
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> a[i][j];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
updateLin(i, 1, 1, m, j, a[i][j]);
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
updateCol(i, 1, 1, n, j, a[j][i]);
char ch;
int poz, lvl;
for (int i = 1; i <= k; i++) {
cin >> ch >> poz >> lvl;
if (ch == 'N') Lasercol(n, 0, poz, lvl);
if (ch == 'S') Lasercol(n, 1, poz, lvl);
if (ch == 'W') Laserlin(m, 0, poz, lvl);
if (ch == 'E') Laserlin(m, 1, poz, lvl);
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
sum[i][j] = a[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
long long ans = 0;
for (int i = p; i <= n; i++)
for (int j = p; j <= m; j++)
ans = max(ans, sum[i][j] - sum[i - p][j] - sum[i][j - p] + sum[i - p][j - p]);
cout << ans;
return 0;
}
Compilation message
ufo.cpp: In function 'void Laserlin(int, bool, int, int)':
ufo.cpp:90:7: warning: variable 'last' set but not used [-Wunused-but-set-variable]
90 | int last = 0;
| ^~~~
ufo.cpp: In function 'void Lasercol(int, bool, int, int)':
ufo.cpp:108:7: warning: variable 'last' set but not used [-Wunused-but-set-variable]
108 | int last = 0;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
3 ms |
492 KB |
Output is correct |
| 4 |
Correct |
27 ms |
748 KB |
Output is correct |
| 5 |
Correct |
179 ms |
3052 KB |
Output is correct |
| 6 |
Correct |
337 ms |
21612 KB |
Output is correct |
| 7 |
Correct |
1305 ms |
52972 KB |
Output is correct |
| 8 |
Correct |
1249 ms |
52972 KB |
Output is correct |
| 9 |
Correct |
1361 ms |
48364 KB |
Output is correct |
| 10 |
Correct |
1367 ms |
52972 KB |
Output is correct |
| 11 |
Correct |
1313 ms |
53132 KB |
Output is correct |
| 12 |
Correct |
1438 ms |
52844 KB |
Output is correct |
| 13 |
Correct |
1728 ms |
60652 KB |
Output is correct |
| 14 |
Correct |
1168 ms |
53100 KB |
Output is correct |
| 15 |
Correct |
1403 ms |
52844 KB |
Output is correct |
| 16 |
Correct |
1517 ms |
53100 KB |
Output is correct |
| 17 |
Execution timed out |
2051 ms |
60780 KB |
Time limit exceeded |
| 18 |
Correct |
1281 ms |
55788 KB |
Output is correct |
| 19 |
Correct |
1434 ms |
62316 KB |
Output is correct |
| 20 |
Execution timed out |
2056 ms |
137452 KB |
Time limit exceeded |
