Submission #341139

#	Time	Username	Problem	Language	Result	Execution time	Memory
341139		amunduzbaev	UFO (IZhO14_ufo)	C++14	30 / 100	2092 ms	17260 KiB

ufo

/** made by amunduzbaev **/
 
#include <bits/stdc++.h>
using namespace std;
 
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define fastios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define vll vector<ll>
#define vii vector<int>
#define vpii vector<pii>
#define vpll vector<pll>
#define cnt(a)__builtin_popcount(a)
template<class T> bool umin(T& a, const T& b) {return a > b? a = b, true:false;}
template<class T> bool umax(T& a, const T& b) {return a < b? a = b, true:false;}
 
const int N = 2e5+5;
const int mod = 1e9+7;
const ll inf = 1e18;
const ld Pi = acos(-1);

int s, n, m, k, ans, sub;

vector<vii> a, pp;

void solve(){
	int n, m, k, p, sub;
	cin>>n>>m>>sub>>k>>p;
	a.resize(n);
	pp.resize(n);
	for(int i=0;i<n;i++){
		a[i].resize(m);
		pp[i].resize(m);
		for(int j=0;j<m;j++) cin>>a[i][j];
	}
	
	for(int i=0;i<k;i++){
		char d;
		cin>>d;
		if(d == 'N'){
			int col, hh, tsub = sub;
			cin>>col>>hh;
			--col;
			for(int j=0;j<n;j++){
				if(a[j][col] >= hh){
					a[j][col]--;
					tsub--; 
					if(!tsub) break;
				}
			}
		}else if(d == 'S'){
			int col, hh, tsub = sub;
			cin>>col>>hh;
			--col;
			for(int j=n-1;j>=0;j--){
				if(a[j][col] >= hh){
					a[j][col]--;
					tsub--; 
					if(!tsub) break;
				}
			}
		}else if(d == 'E'){
			int rr, hh, ts = sub;
			cin>>rr>>hh;
			--rr;
			for(int j=m-1;j>=0;j--){
				if(a[rr][j] >= hh){
					a[rr][j]--;
					ts--;
					if(!ts) break;
				}
			}
		}else{
			int rr, hh, ts = sub;
			cin>>rr>>hh;
			--rr;
			for(int j=0;j<m;j++){
				if(a[rr][j] >= hh){
					a[rr][j]--;
					ts--;
					if(!ts) break;
				}
			}
		}	
	}
	vii rr(n), cc(m);
	
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(i&&j) pp[i][j] += pp[i-1][j-1] + rr[i] + cc[j] + a[i][j];
			else if(i) pp[i][j] = cc[j] + a[i][j];
			else if(j) pp[i][j] = rr[i] + a[i][j];
			else pp[i][j] = a[i][j];
			rr[i] += a[i][j];
			cc[j] += a[i][j];
		}
	}
	
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(i >= p && j >= p){
				int tmp = pp[i][j] - pp[i-p][j] - pp[i][j-p] + pp[i-p][j-p];
				umax(ans, tmp);
			}else if(i == p-1 && j == p-1) umax(ans, pp[i][j]);
			else if(i == p-1) umax(ans, pp[i][j] - pp[i][j-p]);
			else if(j == p-1) umax(ans, pp[i][j] - pp[i-1][j]);
		}
	}
	cout<<ans;
	return;
}

int main(){
	fastios
	int t = 0;
	if(!t) solve();
	else {
		cin>>t;
		while (t--) solve();
	}
	return 0;
}

• Subtask 1: 30 / 100