oj.uz

Submission #337949

# Submission time Handle Problem Language Result Execution time Memory
337949 2020-12-22T06:59:42 Z kutbilim_one UFO (IZhO14_ufo) C++14
40 / 100
 2000 ms 27100 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                  */ 
 
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m, r, k, p;
    cin >> n >> m >> r >> k >> p;
    
    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];
 
    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];
			}
		}
	}
 
	vector< vector<int> > sums(n+1, vector<int>(m+1, 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];
        }
	}

	int 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;
 
    return 0;
}

Subtask #1
40.0 / 100.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 1 ms 364 KB Output is correct
4 Incorrect 5 ms 620 KB Output isn't correct
5 Correct 18 ms 2028 KB Output is correct
6 Correct 75 ms 11372 KB Output is correct
7 Correct 158 ms 27100 KB Output is correct
8 Correct 1084 ms 23772 KB Output is correct
9 Execution timed out 2080 ms 11876 KB Time limit exceeded
10 Execution timed out 2085 ms 12508 KB Time limit exceeded
11 Execution timed out 2082 ms 12224 KB Time limit exceeded
12 Execution timed out 2070 ms 12656 KB Time limit exceeded
13 Execution timed out 2086 ms 16108 KB Time limit exceeded
14 Execution timed out 2032 ms 12736 KB Time limit exceeded
15 Execution timed out 2025 ms 13256 KB Time limit exceeded
16 Correct 1635 ms 24528 KB Output is correct
17 Execution timed out 2063 ms 18796 KB Time limit exceeded
18 Execution timed out 2084 ms 17788 KB Time limit exceeded
19 Execution timed out 2080 ms 14160 KB Time limit exceeded
20 Execution timed out 2073 ms 25944 KB Time limit exceeded