답안 #337620

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
337620	2020-12-21T09:24:45 Z	kutbilim_one	UFO (IZhO14_ufo)	C++14	40 / 100	2000 ms	23788 KB

ufo

/** 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+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;
 
    return 0;
}

Subtask #1

40.0 / 100.0

#	결과	실행 시간	메모리	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	492 KB	Output isn't correct
5	Correct	19 ms	1388 KB	Output is correct
6	Correct	75 ms	8044 KB	Output is correct
7	Correct	156 ms	21848 KB	Output is correct
8	Correct	939 ms	21884 KB	Output is correct
9	Execution timed out	2052 ms	8940 KB	Time limit exceeded
10	Execution timed out	2094 ms	9708 KB	Time limit exceeded
11	Execution timed out	2089 ms	9792 KB	Time limit exceeded
12	Execution timed out	2088 ms	9708 KB	Time limit exceeded
13	Execution timed out	2088 ms	12908 KB	Time limit exceeded
14	Execution timed out	2090 ms	9792 KB	Time limit exceeded
15	Execution timed out	2093 ms	9708 KB	Time limit exceeded
16	Correct	1467 ms	23360 KB	Output is correct
17	Execution timed out	2095 ms	12908 KB	Time limit exceeded
18	Execution timed out	2088 ms	16236 KB	Time limit exceeded
19	Execution timed out	2093 ms	11728 KB	Time limit exceeded
20	Execution timed out	2053 ms	23788 KB	Time limit exceeded