답안 #341147

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
341147 2020-12-29T04:08:04 Z juggernaut UFO (IZhO14_ufo) C++14
100 / 100
1561 ms 133484 KB
#include<bits/stdc++.h>
using namespace std;
int remain;
vector<int>vec;
struct data{
	vector<int>t;
	void reset(int n){t.resize(n<<2);}
	void update(int v,int tl,int tr,int pos, int val){
		if(tl==tr){
			t[v]=val;
			return;
		}
		int mid=(tl+tr)>>1;
		if(pos<=mid)update(v<<1,tl,mid,pos,val);
		else update(v<<1|1,mid+1,tr,pos,val);
		t[v]=max(t[v<<1],t[v<<1|1]);
	}
	void findfirst(int v,int tl,int tr,int x){
		if(remain==0||t[v]<x)return;
		if(tl==tr){
			remain--;
			vec.push_back(tl);
			return;
		}
		int mid=(tl+tr)>>1;
		findfirst(v<<1,tl,mid,x);
		findfirst(v<<1|1,mid+1,tr,x);
	}
	void findlast(int v,int tl,int tr,int x){
		if(remain==0||t[v]<x)return;
		if(tl==tr){
			remain--;
			vec.push_back(tl);
			return;
		}
		int mid=(tl+tr)>>1;
		findlast(v<<1|1,mid+1,tr,x);
		findlast(v<<1,tl,mid,x);
	}
};
data row[1000005],col[1000005];
int main(){
	int n,m,r,k,p;
	scanf("%d%d%d%d%d",&n,&m,&r,&k,&p);
	int a[n+5][m+5];
	memset(a,0,sizeof(a));
	for(int i=1;i<=m;i++)col[i].reset(n+1);
	for(int i=1;i<=n;i++){
		row[i].reset(m+1);
		for(int j=1;j<=m;j++){
			scanf("%d",&a[i][j]);
			row[i].update(1,1,m,j,a[i][j]);
			col[j].update(1,1,n,i,a[i][j]);
		}
	}
	char ch;
	int id,h;
	while(k--){
		vec.clear();
		remain=r;
		cin>>ch;
		scanf("%d%d", &id, &h);
		if(ch=='W'){
			row[id].findfirst(1,1,m,h);
			for(auto to:vec){
				a[id][to]--;
				row[id].update(1,1,m,to,a[id][to]);
				col[to].update(1,1,n,id,a[id][to]);
			}
		}
		if(ch=='N'){
			col[id].findfirst(1,1,n,h);
			for(auto to:vec){
				a[to][id]--;
				row[to].update(1,1,m,id,a[to][id]);
				col[id].update(1,1,n,to,a[to][id]);
			}
		}
		if(ch=='E'){
			row[id].findlast(1,1,m,h);
			for(auto to:vec){
				a[id][to]--;
				row[id].update(1,1,m,to,a[id][to]);
				col[to].update(1,1,n,id,a[id][to]);
			}
		}
		if(ch=='S'){
			col[id].findlast(1,1,n,h);
			for(auto to:vec){
				a[to][id]--;
				row[to].update(1,1,m,id,a[to][id]);
				col[id].update(1,1,n,to,a[to][id]);
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			int x=0,y=0;
			if(j>=2)y=a[i][j-1];
			if(i>=2)x=a[i-1][j];
			a[i][j]=a[i][j]+x+y-a[i-1][j-1];
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(i>=p&&j>=p)
				ans=max(ans,a[i][j]-a[i][j-p]-a[i-p][j]+a[i-p][j-p]);
	cout<<ans;
}

Compilation message

ufo.cpp: In function 'int main()':
ufo.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   44 |  scanf("%d%d%d%d%d",&n,&m,&r,&k,&p);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ufo.cpp:51:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   51 |    scanf("%d",&a[i][j]);
      |    ~~~~~^~~~~~~~~~~~~~~
ufo.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   62 |   scanf("%d%d", &id, &h);
      |   ~~~~~^~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 47340 KB Output is correct
2 Correct 30 ms 47340 KB Output is correct
3 Correct 32 ms 47340 KB Output is correct
4 Correct 47 ms 47596 KB Output is correct
5 Correct 135 ms 49260 KB Output is correct
6 Correct 307 ms 64588 KB Output is correct
7 Correct 445 ms 87660 KB Output is correct
8 Correct 407 ms 87660 KB Output is correct
9 Correct 664 ms 85228 KB Output is correct
10 Correct 779 ms 87660 KB Output is correct
11 Correct 573 ms 87148 KB Output is correct
12 Correct 804 ms 87780 KB Output is correct
13 Correct 977 ms 87660 KB Output is correct
14 Correct 827 ms 87276 KB Output is correct
15 Correct 969 ms 87660 KB Output is correct
16 Correct 410 ms 87148 KB Output is correct
17 Correct 1392 ms 87532 KB Output is correct
18 Correct 388 ms 83180 KB Output is correct
19 Correct 540 ms 92652 KB Output is correct
20 Correct 1561 ms 133484 KB Output is correct