Submission #171913

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
171913	2019-12-30T15:36:39 Z	Nightmar	UFO (IZhO14_ufo)	C++17	35 / 100	2000 ms	39520 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

35.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	2 ms	376 KB	Output is correct
4	Correct	6 ms	504 KB	Output is correct
5	Correct	20 ms	1272 KB	Output is correct
6	Correct	89 ms	8184 KB	Output is correct
7	Execution timed out	2048 ms	18408 KB	Time limit exceeded
8	Execution timed out	2057 ms	18408 KB	Time limit exceeded
9	Execution timed out	2077 ms	17136 KB	Time limit exceeded
10	Execution timed out	2048 ms	18408 KB	Time limit exceeded
11	Execution timed out	2075 ms	18252 KB	Time limit exceeded
12	Execution timed out	2062 ms	18408 KB	Time limit exceeded
13	Execution timed out	2081 ms	23800 KB	Time limit exceeded
14	Correct	1374 ms	18380 KB	Output is correct
15	Execution timed out	2078 ms	18404 KB	Time limit exceeded
16	Execution timed out	2053 ms	18252 KB	Time limit exceeded
17	Execution timed out	2063 ms	23800 KB	Time limit exceeded
18	Execution timed out	2070 ms	24824 KB	Time limit exceeded
19	Execution timed out	2067 ms	20696 KB	Time limit exceeded
20	Execution timed out	2078 ms	39520 KB	Time limit exceeded