제출 #1278081

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1278081		Petrix	UFO (IZhO14_ufo)	C++20	100 / 100	505 ms	149184 KiB

ufo

#include<iostream>
#include<vector>
using namespace std;

#define int long long

//ifstream cin("ufo.in");
//ofstream cout("ufo.out");

int ram;
vector<int>v;
vector<vector<int>> a;

struct arbint{
	vector<int> aint;
	void curata(int n){
	    aint.resize(4*n);
    }
	void update(int nod,int st,int dr,int poz,int val){
		if(st==dr){
			aint[nod]=val;
			return;
		}
		int mij=(st+dr)/2;
		if(poz<=mij)update(2*nod,st,mij,poz,val);
		else update(2*nod+1,mij+1,dr,poz,val);
		aint[nod]=max(aint[2*nod],aint[2*nod+1]);
	}
	void gas_prim(int nod,int st,int dr,int a){
		if(!ram || aint[nod]<a)return;
		if(st==dr){
			ram--;
			v.push_back(st);
			return;
		}
		int mij=(st+dr)/2;
		gas_prim(2*nod,st,mij,a);
		gas_prim(2*nod+1,mij+1,dr,a);
	}
	void gas_ult(int nod,int st,int dr,int a){
		if(!ram || aint[nod]<a)return;
		if(st==dr){
			ram--;
			v.push_back(st);
			return;
		}
		int mij=(st+dr)/2;
		gas_ult(2*nod+1,mij+1,dr,a);
		gas_ult(2*nod,st,mij,a);
	}
}lin[1000005],col[1000005];

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int i,j,n,m,r,k,p,ina,poz,rasp=0;char ch;
	cin>>n>>m>>r>>k>>p;
	a.resize(n+1);a[0].resize(m+1);
	for(i=1;i<=m;i++){
        col[i].curata(n+1);a[0][i]=0;
    }
	for(i=1;i<=n;i++){
		lin[i].curata(m+1);a[i].resize(m+1);
		a[i][0]=0;
		for(j=1;j<=m;j++){
			cin>>a[i][j];
			lin[i].update(1,1,m,j,a[i][j]);
			col[j].update(1,1,n,i,a[i][j]);
		}
	}

	while(k){k--;
		v.clear();
		ram=r;///printf("a");
		cin>>ch>>poz>>ina;
		if(ch=='W'){
			lin[poz].gas_prim(1,1,m,ina);
			for(auto it:v){
				a[poz][it]--;
				lin[poz].update(1,1,m,it,a[poz][it]);
				col[it].update(1,1,n,poz,a[poz][it]);
			}
		}else if(ch=='N'){
			col[poz].gas_prim(1,1,n,ina);
			for(auto it:v){
				a[it][poz]--;
				lin[it].update(1,1,m,poz,a[it][poz]);
				col[poz].update(1,1,n,it,a[it][poz]);
			}
		}else if(ch=='E'){
            lin[poz].gas_ult(1,1,m,ina);
			for(auto it:v){
				a[poz][it]--;
				lin[poz].update(1,1,m,it,a[poz][it]);
				col[it].update(1,1,n,poz,a[poz][it]);
			}
		}else{
			col[poz].gas_ult(1,1,n,ina);
			for(auto it:v){
				a[it][poz]--;
				lin[it].update(1,1,m,poz,a[it][poz]);
				col[poz].update(1,1,n,it,a[it][poz]);
			}
		}
	}
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			a[i][j]+=a[i][j-1]+a[i-1][j]-a[i-1][j-1];
		}
	}
	for(i=p;i<=n;i++){
		for(j=p;j<=m;j++){
            rasp=max(rasp,a[i][j]-a[i][j-p]-a[i-p][j]+a[i-p][j-p]);
		}
    }
	cout<<rasp;
}

• Subtask 1: 100 / 100