Submission #171911

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
171911	2019-12-30T15:34:14 Z	Nightmar	UFO (IZhO14_ufo)	C++17	20 / 100	2000 ms	41644 KB

ufo

#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <iomanip>

#define SWS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pb push_back
#define ppb pop_back
#define ft first
#define sd second
#define read freopen("input.txt", "r", stdin)
#define write freopen("output.txt", "w", stdout)
#define files read; write

using namespace std;

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

const int Z = (int)1e3 + 228;
const int N = (int)1e5 + 228;
const int INF = (int)1e9 + 228;
const int MOD = (int)1e9 + 7;

ll get_pref(vector<vector<ll> > pref, int x1, int y1, int x2, int y2)
{
	return pref[x2][y2] - pref[x1 - 1][y2] - pref[x2][y1 - 1] + pref[x1 - 1][y1 - 1];
}

int main()
{
	SWS;
	//files;
	int n, m, r, k, p;
	cin >> n >> m >> r >> k >> p;
	vector<vector<ll> > a(n + 1, vector<ll> (m + 1));
	vector<vector<ll> > pref(n + 1, vector<ll> (m + 1));
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cin >> a[i][j];
	while (k--)
	{
		char t;
		int num, h, cnt = 0;
		cin >> t >> num >> h;
		if (t == 'N')
		{
			for (int i = 1; i <= n; i++)
			{
				if (cnt == r) break;
				if (a[i][num] >= h)
				{
					a[i][num]--;
					cnt++;
				}
			}
		}
		else if (t == 'S')
		{
			for (int i = n; i > 0; i--)
			{
				if (cnt == r) break;
				if (a[i][num] >= h)
				{
					a[i][num]--;
					cnt++;
				}
			}
		}
		else if (t == 'W')
		{
			for (int i = 1; i <= m; i++)
			{
				if (cnt == r) break;
				if (a[num][i] >= h)
				{
					a[num][i]--;
					cnt++;
				}
			}
		}
		else
		{
			for (int i = m; i > 0; i--)
			{
				if (cnt == r) break;
				if (a[num][i] >= h)
				{
					a[num][i]--;
					cnt++;
				}
			}
		}
	}
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			pref[i][j] = pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1] + a[i][j];
	ll ans = 0;
	for (int i = p; i <= n; i++)
		for (int j = p; j <= m; j++)
			ans = max(ans, get_pref(pref, i - p + 1, j - p + 1, i, j));
	cout << ans;
	return 0;
}

Subtask #1

20.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	11 ms	376 KB	Output is correct
4	Correct	86 ms	860 KB	Output is correct
5	Execution timed out	2062 ms	2620 KB	Time limit exceeded
6	Execution timed out	2064 ms	14748 KB	Time limit exceeded
7	Execution timed out	2068 ms	24548 KB	Time limit exceeded
8	Execution timed out	2052 ms	21112 KB	Time limit exceeded
9	Execution timed out	2049 ms	19656 KB	Time limit exceeded
10	Execution timed out	2061 ms	21224 KB	Time limit exceeded
11	Execution timed out	2058 ms	20552 KB	Time limit exceeded
12	Execution timed out	2063 ms	21352 KB	Time limit exceeded
13	Execution timed out	2028 ms	26944 KB	Time limit exceeded
14	Execution timed out	2024 ms	30100 KB	Time limit exceeded
15	Execution timed out	2055 ms	22248 KB	Time limit exceeded
16	Execution timed out	2021 ms	20676 KB	Time limit exceeded
17	Execution timed out	2037 ms	29748 KB	Time limit exceeded
18	Execution timed out	2052 ms	26872 KB	Time limit exceeded
19	Execution timed out	2054 ms	23172 KB	Time limit exceeded
20	Execution timed out	2075 ms	41644 KB	Time limit exceeded