Submission #341115

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
341115	2020-12-29T03:05:36 Z	tengiz05	UFO (IZhO14_ufo)	C++17	25 / 100	2000 ms	14700 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 a[N][N], n, m, k, r, P;
int pr[N][N];
void solve(int test_case){
	int i, j;
	cin >> n >> m >> r >> k >> P;
	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

25.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	492 KB	Output is correct
3	Correct	1 ms	876 KB	Output is correct
4	Correct	5 ms	1516 KB	Output is correct
5	Incorrect	19 ms	1260 KB	Output isn't correct
6	Correct	72 ms	14700 KB	Output is correct
7	Execution timed out	2061 ms	7532 KB	Time limit exceeded
8	Execution timed out	2079 ms	3948 KB	Time limit exceeded
9	Execution timed out	2031 ms	3564 KB	Time limit exceeded
10	Execution timed out	2086 ms	3948 KB	Time limit exceeded
11	Execution timed out	2066 ms	3820 KB	Time limit exceeded
12	Execution timed out	2095 ms	3948 KB	Time limit exceeded
13	Runtime error	20 ms	9196 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
14	Incorrect	1272 ms	5740 KB	Output isn't correct
15	Execution timed out	2080 ms	5228 KB	Time limit exceeded
16	Execution timed out	2089 ms	3948 KB	Time limit exceeded
17	Runtime error	20 ms	9324 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
18	Runtime error	20 ms	9068 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
19	Execution timed out	2079 ms	4428 KB	Time limit exceeded
20	Execution timed out	2048 ms	10348 KB	Time limit exceeded