Submission #345204

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
345204	2021-01-07T06:45:40 Z	maskoff	UFO (IZhO14_ufo)	C++14	35 / 100	2000 ms	12012 KB

ufo

#include <bits/stdc++.h>

#define file ""

#define all(x) x.begin(), x.end()

#define sc second
#define fr first

#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const ll inf = 1e18 + 5;
const ll mod = 1e9 + 7;

const int N = 5e5 + 5;

int dx[] = {+1, 0, -1, 0};
int dy[] = {0, +1, 0, -1};

int n, m, r, k, p;
vector<vector<int>> c;

void solve1(int x, int h) {
	int cnt = r;
	for (int i = 1; i <= m; i++) {
	 	if (cnt == 0) return;
	 	if (c[x][i] >= h) c[x][i]--, cnt--;
	}
}

void solve2(int x, int h) {
 	int cnt = r;
 	for (int i = m; i >= 1; i--) {
 	 	if (cnt == 0) return;
 	 	if (c[x][i] >= h) c[x][i]--, cnt--;
 	}
}

void solve3(int x, int h) {
  int cnt = r;
  for (int i = n; i >= 1; i--) {
   	if (cnt == 0) return;
   	if (c[i][x] >= h) c[i][x]--, cnt--;
  }
}

void solve4(int x, int h) {
 	int cnt = r;
 	for (int i = 1; i <= n; i++) {
 	 	if (cnt == 0) return;
 	 	if (c[i][x] >= h) c[i][x]--, cnt--;
 	}
}

void update(char x) {
 	int a, b;
 	cin >> a >> b;
 	if (x == 'W') solve1(a, b);
 	if (x == 'E') solve2(a, b);
 	if (x == 'S') solve3(a, b);
 	if (x == 'N') solve4(a, b);
}

int get(int x, int y, int a, int b) {
	int res = 0;
	for (int i = x; i <= a; i++)
		for (int j = y; j <= b; j++)
			res += c[i][j];
	return res;
}

void solve() {
	int mx = 0;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) 
		 	if (i + p - 1 <= n && j + p - 1 <= m) 
		 	 	mx = max(mx, get(i, j, i + p - 1, j + p - 1));
	cout << mx, exit(0);
}	


int main() {   
	ios_base :: sync_with_stdio(false);               
	cin.tie(nullptr);
	srand(time(nullptr));
	cin >> n >> m >> r >> k >> p;
	c.resize(n + 1, vector<int> (m + 1));
	
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cin >> c[i][j];
	
	while (k--) {
	 	char t;
	 	cin >> t;
	 	update(t);
	}
	solve();
  return 0;
}

Subtask #1

35.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	Correct	5 ms	364 KB	Output is correct
5	Correct	17 ms	620 KB	Output is correct
6	Correct	76 ms	2284 KB	Output is correct
7	Execution timed out	2080 ms	5100 KB	Time limit exceeded
8	Execution timed out	2084 ms	5100 KB	Time limit exceeded
9	Execution timed out	2072 ms	4588 KB	Time limit exceeded
10	Execution timed out	2093 ms	5248 KB	Time limit exceeded
11	Execution timed out	2054 ms	5100 KB	Time limit exceeded
12	Execution timed out	2090 ms	5100 KB	Time limit exceeded
13	Execution timed out	2084 ms	9068 KB	Time limit exceeded
14	Correct	1973 ms	5004 KB	Output is correct
15	Execution timed out	2008 ms	5100 KB	Time limit exceeded
16	Execution timed out	2062 ms	5100 KB	Time limit exceeded
17	Execution timed out	2075 ms	9008 KB	Time limit exceeded
18	Execution timed out	2070 ms	8812 KB	Time limit exceeded
19	Execution timed out	2066 ms	5868 KB	Time limit exceeded
20	Execution timed out	2079 ms	12012 KB	Time limit exceeded