Submission #1133927

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133927		Muhammet	UFO (IZhO14_ufo)	C++20	100 / 100	1045 ms	94200 KiB

ufo

#include "bits/stdc++.h"

using namespace std;

#define ll long long

vector <vector <int>> a, st[4];

int n, m, R, k, p, ind;

int bld(int nd, int l, int r, int t, int rc){
	if(l == r) {
		if(t == 0) st[t][rc][nd] = a[l][rc];
		else st[t][rc][nd] = a[rc][l];
		return st[t][rc][nd];
	}
	int md = (l + r) / 2;
	return st[t][rc][nd] = max(bld(nd*2,l,md,t,rc), bld(nd*2+1,md+1,r,t,rc));
}

int fnd(int nd, int l, int r, int rc, int t1, int t2, int x){
	if((st[t1][rc][nd] < x) or (r <= ind and t2 == 0) or (l >= ind and t2 == 1)) return 0;
	if(l == r) return l;
	int md = (l + r) / 2;
	if(t2 == 0){
		int in = fnd(nd*2,l,md,rc,t1,t2,x);
		if(in != 0) return in;
		return fnd(nd*2+1,md+1,r,rc,t1,t2,x);
	}
	int in = fnd(nd*2+1,md+1,r,rc,t1,t2,x);
	if(in != 0) return in;
	return fnd(nd*2,l,md,rc,t1,t2,x);
}

int upd(int nd, int l, int r, int t, int rc, int in){
	if(l > in or r < in) return st[t][rc][nd];
	if(l == r) return st[t][rc][nd] = st[t][rc][nd]-1;
	int md = (l + r) / 2;
	return st[t][rc][nd] = max(upd(nd*2,l,md,t,rc,in), upd(nd*2+1,md+1,r,t,rc,in));
}

void fn(int nd, int l, int r, int t, int rc){
	if(l == r){
		a[rc][l] = st[t][rc][nd];
		return;
	}
	int md = (l + r) / 2;
	fn(nd*2,l,md,t,rc), fn(nd*2+1,md+1,r,t,rc);
}

int main(){
	ios::sync_with_stdio(false); cin.tie(nullptr);

	cin >> n >> m >> R >> k >> p;
	a.resize(n+1, vector <int> (m+1));
	st[0].resize(m+1), st[1].resize(n+1);
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin >> a[i][j];
		}
	}
	for(int i = 1; i <= m; i++){
		st[0][i].resize((n+1)*4);
		bld(1,1,n,0,i);
	}
	for(int i = 1; i <= n; i++){
		st[1][i].resize((m+1)*4);
		bld(1,1,m,1,i);
	}
	for(int i = 1; i <= k; i++){
		char c;
		int rc, x;
		cin >> c >> rc >> x;
		int c1, c2;
		if(c == 'N') c1 = 0, c2 = 0;
		if(c == 'W') c1 = 1, c2 = 0;
		if(c == 'S') c1 = 0, c2 = 1;
		if(c == 'E') c1 = 1, c2 = 1;
		if(c2 == 0) ind = 0;
		else ind = max(n,m)+1;
		for(int j = 1; j <= R; j++){
			ind = fnd(1,1,(!c1 ? n : m),rc,c1,c2,x);
			if(ind == 0) break;
			if(c1 == 0){
				upd(1,1,n,0,rc,ind);
				upd(1,1,m,1,ind,rc);
			}
			else {
				upd(1,1,m,1,rc,ind);
				upd(1,1,n,0,ind,rc);
			}
		}
	}
	for(int i = 1; i <= n; i++){
		fn(1,1,m,1,i);
	}
	ll ans = 0;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			ll x = 0;
			if(i+p-1 > n or j+p-1 > m) continue;
			for(int i1 = i; i1 < i+p; i1++){
				for(int j1 = j; j1 < j+p; j1++){
					x += a[i1][j1];
				}
			}
			ans = max(ans, x);
		}
	}
	cout << ans << '\n';
}

• Subtask 1: 100 / 100