| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 337953 |
2020-12-22T07:11:17 Z |
kutbilim_one |
UFO (IZhO14_ufo) |
C++14 |
|
2000 ms |
12524 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(){
int a[1+n][1+m];
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++) cin >> a[i][j];
vector<int> maxi(n+1, -1), maxj(m+1, -1);
while(k--){
char side;
int pos, h;
cin >> side >> pos >> h;
int shots = r;
if(side == 'W' && (maxi[pos] == -1 || maxi[pos] >= h)){
for(int j = 1; j <= m && shots > 0; j++){
if(a[pos][j] >= h) a[pos][j]--, shots--;
if(maxi[pos] == -1 || maxi[pos] < a[pos][j]) maxi[pos] = a[pos][j];
}
}else if(side == 'E' && (maxi[pos] == -1 || maxi[pos] >= h)){
for(int j = m; j >= 1 && shots > 0; j--){
if(a[pos][j] >= h) a[pos][j]--, shots--;
if(maxi[pos] == -1 || maxi[pos] < a[pos][j]) maxi[pos] = a[pos][j];
}
}else if(side == 'N' && (maxj[pos] == -1 || maxj[pos] >= h)){
for(int i = 1; i <= n && shots > 0; i++){
if(a[i][pos] >= h) a[i][pos]--, shots--;
if(maxj[pos] == -1 || maxj[pos] < a[i][pos]) maxj[pos] = a[i][pos];
}
}else if(side == 'S' && (maxj[pos] == -1 || maxj[pos] >= h)){
for(int i = n; i >= 1 && shots > 0; i--){
if(a[i][pos] >= h) a[i][pos]--, shots--;
if(maxj[pos] == -1 || maxj[pos] < a[i][pos]) maxj[pos] = a[i][pos];
}
}
}
long long sums[1+n][1+m] = {{0}};
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
sums[i][j] += a[i][j] + sums[i][j-1];
}
}
long long maxx = 0;
for(int j = 1; j <= m; j++){
for(int i = 1; i <= n; i++){
sums[i][j] += sums[i-1][j];
if(i >= p && j >= p) maxx = max(maxx, sums[i][j]-sums[i][j-p]-sums[i-p][j]+sums[i-p][j-p]);
}
}
cout << maxx;
}
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 < 50000) solve2();
else sovle1();
return 0;
}
Compilation message
ufo.cpp: In function 'void solve2()':
ufo.cpp:70:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
70 | for(int i = 1; i <= n; i++)
| ^~~
ufo.cpp:73:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
73 | 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 |
4 ms |
364 KB |
Output is correct |
| 5 |
Correct |
17 ms |
1004 KB |
Output is correct |
| 6 |
Correct |
68 ms |
6124 KB |
Output is correct |
| 7 |
Correct |
142 ms |
12524 KB |
Output is correct |
| 8 |
Correct |
651 ms |
12524 KB |
Output is correct |
| 9 |
Execution timed out |
2085 ms |
4460 KB |
Time limit exceeded |
| 10 |
Execution timed out |
2075 ms |
4720 KB |
Time limit exceeded |
| 11 |
Execution timed out |
2088 ms |
4588 KB |
Time limit exceeded |
| 12 |
Execution timed out |
2096 ms |
4716 KB |
Time limit exceeded |
| 13 |
Execution timed out |
2076 ms |
4972 KB |
Time limit exceeded |
| 14 |
Execution timed out |
2099 ms |
4624 KB |
Time limit exceeded |
| 15 |
Execution timed out |
2068 ms |
4716 KB |
Time limit exceeded |
| 16 |
Correct |
995 ms |
12140 KB |
Output is correct |
| 17 |
Execution timed out |
2088 ms |
4972 KB |
Time limit exceeded |
| 18 |
Correct |
1286 ms |
12036 KB |
Output is correct |
| 19 |
Execution timed out |
2052 ms |
5100 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2074 ms |
8172 KB |
Time limit exceeded |
