| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 338065 |
2020-12-22T11:59:49 Z |
kutbilim_one |
UFO (IZhO14_ufo) |
C++14 |
|
1797 ms |
262148 KB |
/** kutbilim.one **/
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
//#define int long long
#define endl '\n'
/*
ifstream in("test.txt");
#define cin in */
int n, m, r, k, p;
void sovle1(){
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> col2[1+m];
set <int> row2[1+n];
set <int> del;
set <int>::iterator it;
int temp, cnt;
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);
row2[i].insert(-j);
col2[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;
int cnt = 0;
for (auto i: col[pos]) {
a[i][pos]--;
if (a[i][pos] == 0) del.insert(i), row[i].erase(pos), row2[i].erase(-pos);
cnt++;if(cnt==r)break;
}
for (auto i: del) {
col[pos].erase(i);
col2[pos].erase(-i);
}
} else if (c == 'S') {
if (col2[pos].empty()) continue;
int cnt = 0;
for (auto i: col2[pos]) {
a[-i][pos]--;
if (a[-i][pos] == 0) del.insert(-i), row[-i].erase(pos), row2[-i].erase(-pos);
cnt++;if(cnt==r)break;
}
for (auto i: del) {
col[pos].erase(i);
col2[pos].erase(-i);
}
} else if (c == 'W') {
if (row[pos].empty()) continue;
int cnt = 0;
for (auto i: row[pos]) {
a[pos][i]--;
if (a[pos][i] == 0) del.insert(i), col[i].erase(pos), col2[i].erase(-pos);
cnt++;if(cnt==r)break;
}
for (auto i: del) {
row[pos].erase(i);
row2[pos].erase(-i);
}
} else {
if (row2[pos].empty()) continue;
int cnt = 0;
for (auto i: row2[pos]) {
a[pos][-i]--;
if (a[pos][-i] == 0) del.insert(-i), col[-i].erase(pos), col2[-i].erase(-pos);
cnt++;if(cnt==r)break;
}
for (auto i: del) {
row[pos].erase(i);
row2[pos].erase(-i);
}
}
del.clear();
}
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';
}
void solve2(){
vector< vector<int> > a(n+1, vector<int>(m+1));
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++) cin >> a[i][j];
while(k--){
char side;
int pos, h;
cin >> side >> pos >> h;
int shots = r;
if(side == 'W'){
for(int j = 1; j <= m && shots > 0; j++)
if(a[pos][j] >= h) a[pos][j]--, shots--;
}else if(side == 'E'){
for(int j = m; j >= 1 && shots > 0; j--)
if(a[pos][j] >= h) a[pos][j]--, shots--;
}else if(side == 'N'){
for(int i = 1; i <= n && shots > 0; i++)
if(a[i][pos] >= h) a[i][pos]--, shots--;
}else{
for(int i = n; i >= 1 && shots > 0; i--)
if(a[i][pos] >= h) a[i][pos]--, shots--;
}
}
vector< vector<int> > sums(n+2, vector<int>(m+1));
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
sums[i][j] += a[i][j] + sums[i][j-1];
}
}
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
sums[j][i] += sums[j-1][i];
}
}
int maxx = 0;
for(int i = p; i <= n; i++){
for(int j = p; j <= m; j++){
maxx = max(maxx, sums[i][j]-sums[i][j-p]-sums[i-p][j]+sums[i-p][j-p]);
}
}
cout << maxx;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> r >> k >> p;
if(n*m < 150000) solve2();
else sovle1();
return 0;
}
Compilation message
ufo.cpp: In function 'void sovle1()':
ufo.cpp:25:8: warning: unused variable 'temp' [-Wunused-variable]
25 | int temp, cnt;
| ^~~~
ufo.cpp:25:14: warning: unused variable 'cnt' [-Wunused-variable]
25 | int temp, cnt;
| ^~~
ufo.cpp: In function 'void solve2()':
ufo.cpp:122:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
122 | for(int i = 1; i <= n; i++)
| ^~~
ufo.cpp:125:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
125 | while(k--){
| ^~~~~
| # |
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 |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
6 ms |
364 KB |
Output is correct |
| 5 |
Correct |
17 ms |
748 KB |
Output is correct |
| 6 |
Incorrect |
637 ms |
96472 KB |
Output isn't correct |
| 7 |
Correct |
1278 ms |
206344 KB |
Output is correct |
| 8 |
Correct |
1589 ms |
206308 KB |
Output is correct |
| 9 |
Correct |
1797 ms |
201256 KB |
Output is correct |
| 10 |
Correct |
1646 ms |
206232 KB |
Output is correct |
| 11 |
Correct |
1279 ms |
200596 KB |
Output is correct |
| 12 |
Correct |
1515 ms |
206436 KB |
Output is correct |
| 13 |
Correct |
1571 ms |
215128 KB |
Output is correct |
| 14 |
Correct |
1103 ms |
200844 KB |
Output is correct |
| 15 |
Incorrect |
1298 ms |
206232 KB |
Output isn't correct |
| 16 |
Correct |
1407 ms |
200644 KB |
Output is correct |
| 17 |
Incorrect |
1214 ms |
214824 KB |
Output isn't correct |
| 18 |
Correct |
1320 ms |
186388 KB |
Output is correct |
| 19 |
Incorrect |
1445 ms |
216356 KB |
Output isn't correct |
| 20 |
Runtime error |
634 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
