| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 334228 |
2020-12-08T17:15:28 Z |
Pety |
UFO (IZhO14_ufo) |
C++14 |
|
1497 ms |
141864 KB |
#include <bits/stdc++.h>
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);
}
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;
while (r1 && aint_lin[poz][1] >= lvl) {
int x = queryLin(ok, 1, 1, dr, poz, lvl);
a[poz][x]--;
updateLin(poz, 1, 1, m, x, a[poz][x]);
updateCol(x, 1, 1, n, poz, a[poz][x]);
r1--;
}
}
void Lasercol (int dr, bool ok, int poz, int lvl) {
int r1 = r;
while (r1 && aint_col[poz][1] >= lvl) {
int x = queryCol(ok, 1, 1, dr, poz, lvl);
a[x][poz]--;
updateCol(poz, 1, 1, n, x, a[x][poz]);
updateLin(x, 1, 1, m, poz, a[x][poz]);
r1--;
}
}
int main()
{
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;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Incorrect |
3 ms |
492 KB |
Output isn't correct |
| 4 |
Incorrect |
31 ms |
876 KB |
Output isn't correct |
| 5 |
Incorrect |
142 ms |
3692 KB |
Output isn't correct |
| 6 |
Incorrect |
381 ms |
24940 KB |
Output isn't correct |
| 7 |
Incorrect |
751 ms |
60836 KB |
Output isn't correct |
| 8 |
Correct |
603 ms |
57244 KB |
Output is correct |
| 9 |
Correct |
896 ms |
51692 KB |
Output is correct |
| 10 |
Correct |
1098 ms |
56340 KB |
Output is correct |
| 11 |
Correct |
829 ms |
56428 KB |
Output is correct |
| 12 |
Correct |
1103 ms |
56684 KB |
Output is correct |
| 13 |
Correct |
1324 ms |
65200 KB |
Output is correct |
| 14 |
Correct |
947 ms |
56300 KB |
Output is correct |
| 15 |
Incorrect |
1024 ms |
58092 KB |
Output isn't correct |
| 16 |
Correct |
630 ms |
58348 KB |
Output is correct |
| 17 |
Incorrect |
1497 ms |
69612 KB |
Output isn't correct |
| 18 |
Correct |
600 ms |
61292 KB |
Output is correct |
| 19 |
Incorrect |
785 ms |
67308 KB |
Output isn't correct |
| 20 |
Correct |
1461 ms |
141864 KB |
Output is correct |
