Submission #341139

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
341139	2020-12-29T03:49:19 Z	amunduzbaev	UFO (IZhO14_ufo)	C++14	30 / 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){
					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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	364 KB	Output is correct
2	Correct	0 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	4 ms	364 KB	Output is correct
5	Correct	17 ms	748 KB	Output is correct
6	Correct	69 ms	4204 KB	Output is correct
7	Execution timed out	2045 ms	8172 KB	Time limit exceeded
8	Execution timed out	2084 ms	8172 KB	Time limit exceeded
9	Execution timed out	2078 ms	8172 KB	Time limit exceeded
10	Execution timed out	2055 ms	8172 KB	Time limit exceeded
11	Execution timed out	2043 ms	7916 KB	Time limit exceeded
12	Execution timed out	2033 ms	8300 KB	Time limit exceeded
13	Execution timed out	2033 ms	14572 KB	Time limit exceeded
14	Execution timed out	2083 ms	7916 KB	Time limit exceeded
15	Execution timed out	2085 ms	8172 KB	Time limit exceeded
16	Execution timed out	2081 ms	7916 KB	Time limit exceeded
17	Execution timed out	2088 ms	14444 KB	Time limit exceeded
18	Execution timed out	2092 ms	17260 KB	Time limit exceeded
19	Execution timed out	2079 ms	8172 KB	Time limit exceeded
20	Execution timed out	2082 ms	8172 KB	Time limit exceeded