oj.uz

답안 #337953

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
337953 2020-12-22T07:11:17 Z kutbilim_one UFO (IZhO14_ufo) C++14
50 / 100
 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--){
      |  ^~~~~

Subtask #1
50.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 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