| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 334255 |
2020-12-08T18:59:10 Z |
Pety |
UFO (IZhO14_ufo) |
C++14 |
|
2000 ms |
137452 KB |
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("O1")
#pragma GCC optimize ("Ofast")
using namespace std;
int n, m, k, r, p, i, j;
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);
}
void updateLin (int poz, int nod, int st, int dr, int pozhatz, int val) {
if (st == dr) {
aint_lin[poz][nod] = val;
return;
}
int 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;
}
int 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;
int 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;
int 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;
vector<int > kasa;
while (r1 && aint_lin[poz][1] >= lvl) {
int x = queryLin(ok, 1, 1 , dr, poz, lvl);
a[poz][x]--;
kasa.push_back(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;
vector<int > kasa;
while (r1 && aint_col[poz][1] >= lvl) {
int x = queryCol(ok, 1, 1, dr, poz, lvl);
a[x][poz]--;
kasa.push_back(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 (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
cin >> a[i][j];
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
updateLin(i, 1, 1, m, j, a[i][j]);
for (i = 1; i <= m; i++)
for (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 (i = 1; i <= n; i++)
for (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 (i = p; i <= n; i++)
for (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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
0 ms |
364 KB |
Output is correct |
| 3 |
Correct |
2 ms |
492 KB |
Output is correct |
| 4 |
Correct |
33 ms |
748 KB |
Output is correct |
| 5 |
Correct |
174 ms |
2924 KB |
Output is correct |
| 6 |
Correct |
342 ms |
21740 KB |
Output is correct |
| 7 |
Correct |
488 ms |
52908 KB |
Output is correct |
| 8 |
Correct |
406 ms |
52972 KB |
Output is correct |
| 9 |
Correct |
938 ms |
48364 KB |
Output is correct |
| 10 |
Correct |
1324 ms |
52972 KB |
Output is correct |
| 11 |
Correct |
881 ms |
53100 KB |
Output is correct |
| 12 |
Correct |
1354 ms |
52972 KB |
Output is correct |
| 13 |
Correct |
1634 ms |
60780 KB |
Output is correct |
| 14 |
Correct |
1134 ms |
52972 KB |
Output is correct |
| 15 |
Correct |
1312 ms |
52972 KB |
Output is correct |
| 16 |
Correct |
434 ms |
53100 KB |
Output is correct |
| 17 |
Correct |
1850 ms |
60780 KB |
Output is correct |
| 18 |
Correct |
406 ms |
55916 KB |
Output is correct |
| 19 |
Correct |
721 ms |
62444 KB |
Output is correct |
| 20 |
Execution timed out |
2083 ms |
137452 KB |
Time limit exceeded |
