Submission #345362

#	Time	Username	Problem	Language	Result	Execution time	Memory
345362		l3nl3	UFO (IZhO14_ufo)	C++14	5 / 100	2080 ms	42732 KiB

ufo

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>  
 
#define exit exit(false)
 
//#define here() cerr << "herewego\n";
#define show(x) cerr << #x << ": " << x << '\n';
 
#define int long long
//#define double long double
 
#define all(a) a.begin(), a.end()
#define whole(a, p, q) a+p, a+p+q
 
#define ioio() ios_base::sync_with_stdio (0); cin.tie (0); cout.tie (0);
 
using namespace std;
 
//using namespace __gnu_pbds;   
//typedef tree <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;  
 
const int mxsz = 1e4 + 7;
 
int n, m, r, k , p, a[mxsz][mxsz], pr[mxsz][mxsz], mx;
char tp;
int x, y, h, sum, cn;
 
signed main () { ioio();
	cin >> n >> m >> r >> k >> p;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
			sum += a[i][j];
		}
	}
	while (k--) {
		cin >> tp >> x >> h;
		x++;
		cn = r;
		y = 1;
		if (tp == 'N') {
			while (y <= n && cn > 0) {
				while (a[y][x] >= h) {
					a[y][x]--;
					cn--;
				}
				y++;
			}
		} else if (tp == 'W') {
			while (y <= m && cn > 0) {
				while (a[x][y] >= h) {
					a[x][y]--;
					cn--;
				}
				y++;
			}
		} else if (tp == 'S') {
			y = n;
			while (y >= 1 && cn > 0) {
				while (a[y][x] >= h) {
					a[y][x]--;
					cn--;
				}
				y--;
			}
		} else {
			y = m;
			while (y >= 1 && cn > 0) {
				if (a[x][y] >= h) {
					a[x][y]--;
					cn--;
				}
				y--;
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			pr[i][j] = pr[i-1][j] + a[i][j];
//			cout << a[i][j] << " \n"[j==m];
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			int pj = j;
			int sum = 0;
			while ((pj - j + 1) <= p) {
				sum += pr[i+(p-1)][pj] - pr[i-1][pj];
				pj++;
			}
			mx = max (mx, sum);
		}
	}
	cout << mx;
}

• Subtask 1: 5 / 100