| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 338170 |
2020-12-22T15:35:37 Z |
boykut |
UFO (IZhO14_ufo) |
C++14 |
|
994 ms |
172632 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m, k, r, p;
cin >> n >> m >> r >> k >> p;
if (n * m <= 500000) {
int a[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> a[i][j];
}
}
for (int i = 0; i < k; i++) {
char ch; cin >> ch;
int pos, h; cin >> pos >> h;
pos--;
if (ch == 'N') {
int cnt = 0;
for (int i = 0; i < n && cnt < r; i++) {
if (a[i][pos] >= h) {
a[i][pos] --;
cnt++;
if (cnt == r) break;
}
}
} else if (ch == 'E') {
int cnt = 0;
for (int i = m - 1; i >= 0 && cnt < r; i--) {
if (a[pos][i] >= h) {
a[pos][i] --;
cnt++;
if (cnt == r) break;
}
}
} else if (ch == 'W') {
int cnt = 0;
for (int i = 0; i < m && cnt < r; i++) {
if (a[pos][i] >= h) {
a[pos][i] --;
cnt++;
if (cnt == r) break;
}
}
} else {
int cnt = 0;
for (int i = n - 1; i >= 0 && cnt < r; i--) {
if (a[i][pos] >= h) {
a[i][pos] --;
cnt++;
if (cnt == r) break;
}
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
//cout << a[i][j] << ' ';
}
//cout << '\n';
}
int sum = 0, ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (i + p <= n && j + p <= m) {
sum = 0;
for (int i1 = i; i1 < i + p; i1++) {
for (int j1 = j; j1 < j + p; j1++) {
sum += a[i1][j1];
}
}
if (sum > ans) {
//cout << i << ' ' << j << '\n';
ans = sum;
//cout << sum << "\n\n";
}
}
}
}
cout << ans << '\n';
} else {
vector < vector <int> > a(1+n, vector <int> (1+m, 0));
vector < vector <int> > sum(1+n, vector <int> (1+m, 0));
set <int> col[1+m];
set <int> row[1+n];
set <int> del;
set <int>::iterator it;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
if (a[i][j] != 0) {
row[i].insert(j);
col[j].insert(i);
}
}
}
for (int tmp = k; tmp--;) {
char c; cin >> c;
int pos, h; cin >> pos >> h;
if (c == 'N') {
if (col[pos].empty()) continue;
it = col[pos].begin();
int cnt = 0;
for (int temp = col[pos].size(); temp--;) {
//if(a[*it][pos]>=h){
a[*it][pos]--;
if (a[*it][pos] == 0) del.insert(*it);
cnt++;if(cnt==r)break;
//}
it++;
}
for (auto i: del) {
col[pos].erase(i);
row[i].erase(pos);
}
} else if (c == 'S') {
if (col[pos].empty()) continue;
it = col[pos].end(); it--;
int cnt = 0;
for (int temp = col[pos].size(); temp--;) {
// if(a[*it][pos]>=h){
a[*it][pos]--;
if (a[*it][pos] == 0) del.insert(*it);
cnt++;if(cnt==r)break;
//}
it--;
}
for (auto i: del) {
col[pos].erase(i);
row[i].erase(pos);
}
} else if (c == 'W') {
if (row[pos].empty()) continue;
it = row[pos].begin();
int cnt = 0;
for (int temp = row[pos].size(); temp--;) {
//if(a[pos][*it]>=h){
a[pos][*it]--;
if (a[pos][*it] == 0) del.insert(*it);
cnt++;if(cnt==r)break;
//}
it++;
}
for (auto i: del) {
row[pos].erase(i);
col[i].erase(pos);
}
} else {
if (row[pos].empty()) continue;
it = row[pos].end(); it--;
int cnt = 0;
for (int temp = row[pos].size(); temp--;) {
//if(a[pos][*it]>=h){
a[pos][*it]--;
if (a[pos][*it] == 0) del.insert(*it);
cnt++;if(cnt==r)break;
//}
it--;
}
for (auto i: del) {
row[pos].erase(i);
col[i].erase(pos);
}
}
while (!del.empty())
del.erase(del.begin());
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
sum[i][j] = a[i][j];
sum[i][j] += sum[i-1][j];
sum[i][j] += sum[i][j-1];
sum[i][j] -= sum[i-1][j-1];
}
}
int ans = 0, A, i2, j2;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
i2 = i + p - 1, j2 = j + p - 1;
if (i2 <= n && j2 <= m) {
A = sum[i2][j2];
A -= sum[i2][j-1];
A -= sum[i-1][j2];
A += sum[i-1][j-1];
if (A > ans)
ans = A;
}
}
}
cout << ans << '\n';
}
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 |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
5 ms |
364 KB |
Output is correct |
| 5 |
Correct |
19 ms |
748 KB |
Output is correct |
| 6 |
Correct |
77 ms |
4204 KB |
Output is correct |
| 7 |
Correct |
559 ms |
116444 KB |
Output is correct |
| 8 |
Correct |
811 ms |
116268 KB |
Output is correct |
| 9 |
Correct |
994 ms |
113148 KB |
Output is correct |
| 10 |
Correct |
813 ms |
116164 KB |
Output is correct |
| 11 |
Correct |
660 ms |
113216 KB |
Output is correct |
| 12 |
Correct |
744 ms |
116188 KB |
Output is correct |
| 13 |
Correct |
861 ms |
122500 KB |
Output is correct |
| 14 |
Correct |
530 ms |
113216 KB |
Output is correct |
| 15 |
Incorrect |
553 ms |
116168 KB |
Output isn't correct |
| 16 |
Correct |
744 ms |
113088 KB |
Output is correct |
| 17 |
Incorrect |
671 ms |
122476 KB |
Output isn't correct |
| 18 |
Correct |
746 ms |
109420 KB |
Output is correct |
| 19 |
Incorrect |
807 ms |
122576 KB |
Output isn't correct |
| 20 |
Correct |
847 ms |
172632 KB |
Output is correct |
