Submission #341117

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
341117	2020-12-29T03:09:57 Z	tengiz05	UFO (IZhO14_ufo)	C++17	35 / 100	2000 ms	39524 KB

ufo

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define PI acos(-1)
#define ld long double
template<class T> bool chmin(T& a, const T& b) {return a>b? a=b, true:false;}
template<class T> bool chmax(T& a, const T& b) {return a<b? a=b, true:false;}
const int mod = 1e9+7, N = 1005;
int msb(int val){return sizeof(int)*8-__builtin_clzll(val)-1;}
int n, m, k, r, P;
void solve(int test_case){
	int i, j;
	cin >> n >> m >> r >> k >> P;
	vector<vector<int>> a(n+1, vector<int> (m+1));
	vector<vector<int>> pr(n+1, vector<int> (m+1));
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			cin >> a[i][j];
		}
	}
	while(k--){
		char typ;
		cin >> typ;
		int pos, height;
		cin >> pos >> height;
		if(typ == 'N'){
			int x=1, y=pos;
			int remaining = r;
			while(x < n && remaining){
				if(a[x][y] >= height){
					a[x][y]--;
					remaining--;
				}x++;
			}
		}else if(typ == 'S'){
			int x=n, y=pos;
			int remaining = r;
			while(x > 0 && remaining){
				if(a[x][y] >= height){
					a[x][y]--;
					remaining--;
				}x--;
			}
		}else if(typ == 'E'){
			int x=pos, y=m;
			int remaining = r;
			while(y > 0 && remaining){
				if(a[x][y] >= height){
					a[x][y]--;
					remaining--;
				}y--;
			}
		}else {
			int x=pos, y=1;
			int remaining = r;
			while(y < m && remaining){
				if(a[x][y] >= height){
					a[x][y]--;
					remaining--;
				}y++;
			}
		}
	}
/*	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			cout << a[i][j] << ' ';
		}cout << '\n';
	}
	*/
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			pr[i][j] = pr[i][j-1] + a[i][j];
		}
		for(j=1;j<=m;j++){
			pr[i][j] += pr[i-1][j];
		}
	}
	int ans = 0;
	for(i=P;i<=n;i++){
		for(j=P;j<=m;j++){
			int area = pr[i][j] + pr[i-P][j-P];
			area -= pr[i-P][j];
			area -= pr[i][j-P];
			chmax(ans, area);
		}
	}cout << ans << '\n';
	return;
}

signed main(){
	FASTIO;
#define MULTITEST 0
#if MULTITEST
	int _T;
	cin >> _T;
	for(int T_CASE = 1; T_CASE <= _T; T_CASE++)
		solve(T_CASE);
#else
	solve(1);
#endif
	return 0;
}

Subtask #1

35.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	492 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	492 KB	Output is correct
5	Correct	19 ms	1260 KB	Output is correct
6	Correct	78 ms	8044 KB	Output is correct
7	Execution timed out	2094 ms	18396 KB	Time limit exceeded
8	Execution timed out	2081 ms	18396 KB	Time limit exceeded
9	Execution timed out	2091 ms	17456 KB	Time limit exceeded
10	Execution timed out	2091 ms	18428 KB	Time limit exceeded
11	Execution timed out	2095 ms	18264 KB	Time limit exceeded
12	Execution timed out	2065 ms	18652 KB	Time limit exceeded
13	Execution timed out	2055 ms	24556 KB	Time limit exceeded
14	Correct	1888 ms	18264 KB	Output is correct
15	Execution timed out	2099 ms	18396 KB	Time limit exceeded
16	Execution timed out	2070 ms	18368 KB	Time limit exceeded
17	Execution timed out	2094 ms	24008 KB	Time limit exceeded
18	Execution timed out	2041 ms	24812 KB	Time limit exceeded
19	Execution timed out	2094 ms	20688 KB	Time limit exceeded
20	Execution timed out	2092 ms	39524 KB	Time limit exceeded