Submission #341281

#	Time	Username	Problem	Language	Result	Execution time	Memory
341281		amunduzbaev	UFO (IZhO14_ufo)	C++14	100 / 100	1042 ms	162264 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 int 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 = 1e5+5;
const int mod = 1e9+7;
const ll inf = 1e18;
const ld Pi = acos(-1);

int n, m, k, ans = 1, cnt, rr, p;
vector<vii> aa;

struct TREE{
	vector<int> tree;
	int s = 2;
	void init(int n, vector<int> vv){
		while(s < n) s<<=1;
		tree.assign(s*2, 0);
		for(int i=s;i<s+sz(vv);i++) tree[i] = vv[i-s];
		for(int i=s-1;i>=1;i--) tree[i] = max(tree[i<<1], tree[(i<<1)+1]); 
	}
	
	vector<int> dd;
	int rr;
	
	void dec(int hh, int lx, int rx, int x){
		if(!rr) return;
		if(lx == rx){
			dd.pb(lx);
			tree[x]--;
			rr--;
			return;
		}
		int m = (lx + rx)>>1;
		if(tree[x<<1] >= hh) dec(hh, lx, m, x<<1);
		tree[x] = max(tree[(x<<1)], tree[(x<<1)+1]);
		if(!rr) return;
		if(tree[(x<<1)+1] >= hh) dec(hh, m+1, rx, (x<<1) +1);
		tree[x] = max(tree[(x<<1)], tree[(x<<1)+1]);
	}
	
	void decr(int hh){
		dd.clear();
		dec(hh, 1, s, 1);
	}
	
	void rdec(int hh, int lx, int rx, int x){
		//cout<<lx<<" "<<rx<<" "<<tree[x]<<" "<<rr<<endl;
		if(lx == rx){
			dd.pb(lx);
			tree[x]--;
			rr--;
			return;
		}
		int m = (lx + rx)>>1;
		if(tree[(x<<1)+1] >= hh) rdec(hh, m+1, rx, (x<<1) +1);
		tree[x] = max(tree[(x<<1)], tree[(x<<1)+1]);
		if(!rr) return;
		if(tree[x<<1] >= hh) rdec(hh, lx, m, x<<1);
		tree[x] = max(tree[x<<1], tree[(x<<1)+1]);
	}
	
	void rdecr(int hh){
		dd.clear();
		rdec(hh, 1, s, 1);
	}
	
	void ssin(int in, int lx, int rx, int x){
		//cout<<lx<<" "<<rx<<" "<<in<<endl;
		if(lx == rx){
			tree[x]--;
			return;
		}int m = (lx + rx)>>1;
		if(in <= m) ssin(in, lx, m, x*2);
		else ssin(in, m+1, rx, x*2+1);
		tree[x] = max(tree[x*2], tree[x*2+1]);
	}
	
	void subin(int in){
		ssin(in, 1, s, 1);
	}
	
	void print(){
		for(int i=1;i<2*s;i++) cout<<tree[i]<<" ";
		cout<<endl;
	}
};

void solve(){
	cin>>n>>m>>rr>>k>>p;
	aa.resize(n);
	for(int i=0;i<n;i++){
		aa[i].resize(m);
		for(int j=0;j<m;j++) cin>>aa[i][j];
	}
	
	vector<TREE> row(n), col(m);
	for(int i=0;i<n;i++) row[i].init(m, aa[i]);
	
	for(int i=0;i<m;i++){
		vii tmp(n);
		for(int j=0;j<n;j++) tmp[j] = aa[j][i];
		col[i].init(n, tmp);
	}
	
	for(int i=0;i<k;i++){
		char dd;
		cin>>dd;
		if(dd == 'N'){
			int in, hh;
			cin>>in>>hh;
			in--;
			col[in].rr = rr;
			col[in].decr(hh);
			vii tmp = col[in].dd;
			for(auto x:tmp) row[x-1].subin(in+1);
		}else if(dd == 'S'){
			int in, hh;
			cin>>in>>hh;
			in--;
			col[in].rr = rr;
			col[in].rdecr(hh);
			vii tmp = col[in].dd;
			for(auto x:tmp) row[x-1].subin(in+1);	
		}else if(dd == 'W'){
			int in, hh;
			cin>>in>>hh;
			in--;
			row[in].rr = rr;
			row[in].decr(hh);
			vii tmp =  row[in].dd;
			for(auto x:tmp) col[x-1].subin(in+1);
		}else {
			int in, hh;
			cin>>in>>hh;
			in--;
			row[in].rr = rr;
			row[in].rdecr(hh);
			vii tmp =  row[in].dd;
			for(auto x:tmp) col[x-1].subin(in+1);
		}
	}
	
	vector<vii> a(n), pp(n);
	for(int i=0;i<n;i++){
		pp[i].resize(m);
		a[i].resize(m);
		for(int j=0;j<m;j++) a[i][j] = row[i].tree[j+(row[i].s)];
	}
	
	vii r(n, 0), cc(m, 0);
	
	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] + r[i] + cc[j] + a[i][j];
			else if(i) pp[i][j] = cc[j] + a[i][j];
			else if(j) pp[i][j] = r[i] + a[i][j];
			else pp[i][j] = a[i][j];
			r[i] += a[i][j];
			cc[j] += a[i][j];
		}
	}
	
	ans = 0;
	for(int i=p-1;i<n;i++){
		for(int j=p-1;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<<"\n";
	return;
}

/*

4 8 2 6 2
1 1 1 1 1 1 1 1
1 2 3 1 1 1 3 1
1 2 1 1 3 1 1 1
1 1 1 1 1 1 1 2
N 2 2
W 2 2
W 2 3
S 2 1
S 4 1
S 7 1

*/

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

Compilation message (stderr)

ufo.cpp:219:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  219 | main(){
      |      ^

• Subtask 1: 100 / 100