Submission #340315

#	Time	Username	Problem	Language	Result	Execution time	Memory
340315		_ani	UFO (IZhO14_ufo)	C++17	30 / 100	483 ms	16620 KiB

ufo

#define BUGOARR(x) { cerr << "{ "; for(auto& i: (x))cerr<<i<<' ';cerr<<"}\n";}
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int rupd[50'002][2], cupd[50'002][2];
vector<vector<int>> a;
int main()
{
	int n, m, r, k, p;
	cin >> n >> m >> r >> k >> p;
	a.resize(n);
	for (int i = 0; i < n; i++)
		a[i].resize(m);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> a[i][j];
	while (k--)
	{
		char d;
		int r, c, t, x;
		cin >> d >> x >> t;
		if (d == 'N' || d == 'S')
		{
			if (d == 'N')
				c = 0;
			else c = 1;
			cupd[x - 1][c]++;
		}
		else
		{
			if (d == 'W')
				r = 0;
			else r = 1;
			rupd[x - 1][r]++;
		}
	}
	for (int i = 0; i < n; i++)
	{
		if (rupd[i][1]) {
			int x = rupd[i][1] * r;
			int j = 0;
			while (x && j < m)
			{
				int tmp = min(a[i][j], min(x, rupd[i][1]));
				a[i][j] -= tmp;
				x -= tmp;
				j++;
			}
		}
		if (rupd[i][0]) {
			int x = rupd[i][0] * r;
			int j = m - 1;
			while (x && j >= 0)
			{
				int tmp = min(a[i][j], min(x, rupd[i][0]));
				a[i][j] -= tmp;
				x -= tmp;
				j--;
			}
		}
	}
	for (int j = 0; j < m; j++)
	{
		if (cupd[j][1]) {
			int x = cupd[j][1] * r;
			int i = 0;
			while (x && i < n)
			{
				int tmp = min(a[i][j], min(x, cupd[j][1]));
				a[i][j] -= tmp;
				x -= tmp;
				i++;
			}
		}
		if (cupd[j][0]) {
			int x = cupd[j][0] * r;
			int i = n - 1;
			while (x && i >= 0)
			{
				int tmp = min(a[i][j], min(x, cupd[j][0]));
				a[i][j] -= tmp;
				x -= tmp;
				i--;
			}
		}
	}/*
	for (auto& x : a)
		BUGOARR(x);*/
	int ans = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
		{
			if (i + p > n || j + p > m)continue;
			int cur = 0;
			for (int l = i; l < i + p; l++)
				for (int r = j; r < j + p; r++)
					cur += a[l][r];
			ans = max(ans, cur);
		}
	cout << ans << '\n';
	return 0;
}

• Subtask 1: 30 / 100