Submission #345204

#	Time	Username	Problem	Language	Result	Execution time	Memory
345204		maskoff	UFO (IZhO14_ufo)	C++14	35 / 100	2093 ms	12012 KiB

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 / 100