| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 334431 |
2020-12-09T06:36:29 Z |
Pety |
UFO (IZhO14_ufo) |
C++14 |
|
1930 ms |
140848 KB |
#include <bits/stdc++.h>
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]);
}
}
void buildLin (int x, int nod, int st, int dr) {
if (st == dr) {
aint_lin[x][nod] = a[x][st];
return;
}
int mij = (st + dr) / 2;
buildLin(x, 2 * nod, st, mij);
buildLin(x, 2 * nod + 1, mij + 1, dr);
aint_lin[x][nod] = max(aint_lin[x][2 * nod], aint_lin[x][2 * nod + 1]);
}
void buildCol (int x, int nod, int st, int dr) {
if (st == dr) {
aint_col[x][nod] = a[st][x];
return;
}
int mij = (st + dr) / 2;
buildCol(x, 2 * nod, st, mij);
buildCol(x, 2 * nod + 1, mij + 1, dr);
aint_col[x][nod] = max(aint_col[x][2 * nod], aint_col[x][2 * nod + 1]);
}
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++)
buildLin(i, 1, 1, m);
for (i = 1; i <= m; i++)
buildCol(i, 1, 1, n);
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 |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
2 ms |
492 KB |
Output is correct |
| 4 |
Correct |
27 ms |
876 KB |
Output is correct |
| 5 |
Correct |
182 ms |
3692 KB |
Output is correct |
| 6 |
Correct |
326 ms |
24944 KB |
Output is correct |
| 7 |
Correct |
303 ms |
56968 KB |
Output is correct |
| 8 |
Correct |
223 ms |
57068 KB |
Output is correct |
| 9 |
Correct |
811 ms |
51692 KB |
Output is correct |
| 10 |
Correct |
1194 ms |
56348 KB |
Output is correct |
| 11 |
Correct |
752 ms |
56124 KB |
Output is correct |
| 12 |
Correct |
1225 ms |
56428 KB |
Output is correct |
| 13 |
Correct |
1520 ms |
64836 KB |
Output is correct |
| 14 |
Correct |
992 ms |
56300 KB |
Output is correct |
| 15 |
Correct |
1146 ms |
57192 KB |
Output is correct |
| 16 |
Correct |
251 ms |
57196 KB |
Output is correct |
| 17 |
Correct |
1804 ms |
64892 KB |
Output is correct |
| 18 |
Correct |
257 ms |
60140 KB |
Output is correct |
| 19 |
Correct |
559 ms |
66540 KB |
Output is correct |
| 20 |
Correct |
1930 ms |
140848 KB |
Output is correct |
