Submission #341136

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
341136	2020-12-29T03:44:47 Z	amunduzbaev	UFO (IZhO14_ufo)	C++14	10 / 100	2000 ms	17260 KB

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){
					int ss = min(a[j][col] - hh+1, tsub);
					a[j][col] -= ss;
					tsub -= ss;
					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){
					int ss = min(a[j][col] - hh+1, tsub);
					a[j][col] -=ss;
					tsub -= ss;
					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){
					int ss = min(a[rr][j] - hh+1, ts);
					a[rr][j] -= ss;
					ts -= ss;
					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){
					int ss = min(a[rr][j] - hh+1, ts);
					a[rr][j] -= ss;
					ts -= ss;
					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

10.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	364 KB	Output is correct
2	Incorrect	1 ms	364 KB	Output isn't correct
3	Incorrect	1 ms	364 KB	Output isn't correct
4	Incorrect	4 ms	364 KB	Output isn't correct
5	Incorrect	15 ms	748 KB	Output isn't correct
6	Incorrect	61 ms	4204 KB	Output isn't correct
7	Execution timed out	2097 ms	8172 KB	Time limit exceeded
8	Execution timed out	2100 ms	8172 KB	Time limit exceeded
9	Execution timed out	2100 ms	8172 KB	Time limit exceeded
10	Execution timed out	2096 ms	8172 KB	Time limit exceeded
11	Execution timed out	2100 ms	7916 KB	Time limit exceeded
12	Execution timed out	2086 ms	8172 KB	Time limit exceeded
13	Execution timed out	2047 ms	14444 KB	Time limit exceeded
14	Correct	254 ms	8576 KB	Output is correct
15	Incorrect	1486 ms	8632 KB	Output isn't correct
16	Execution timed out	2094 ms	7916 KB	Time limit exceeded
17	Execution timed out	2094 ms	14444 KB	Time limit exceeded
18	Execution timed out	2091 ms	17260 KB	Time limit exceeded
19	Execution timed out	2091 ms	8172 KB	Time limit exceeded
20	Execution timed out	2081 ms	8172 KB	Time limit exceeded