oj.uz

답안 #31473

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
31473 2017-08-28T16:19:31 Z Kerim UFO (IZhO14_ufo) C++14
100 / 100
 1216 ms 119264 KB 
#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
const int N=1e6+9;
struct myTree{
	vector<int>s;
	void upd(int p,int v,int nd,int x,int y){
		if(x==y){
			s[nd]=v;
			return;
		}
		int mid=(x+y)>>1;
		if(p<=mid)
			upd(p,v,nd<<1,x,mid);
		else
			upd(p,v,nd<<1|1,mid+1,y);
		s[nd]=max(s[nd<<1],s[nd<<1|1]);	
	}
	int getL(int l,int r,int v,int nd,int x,int y){
		if(l>y or x>r or s[nd]<v)
			return -1;	
		if(x==y)
			return x;
		int mid=(x+y)>>1;
		int val=getL(l,r,v,nd<<1,x,mid);
		if(~val)
			return val;
		return getL(l,r,v,nd<<1|1,mid+1,y);	
	}
	int getR(int l,int r,int v,int nd,int x,int y){
		if(l>y or x>r or s[nd]<v)
			return -1;	
		if(x==y)
			return x;
		int mid=(x+y)>>1;
		int val=getR(l,r,v,nd<<1|1,mid+1,y);
		if(~val)
			return val;
		return getR(l,r,v,nd<<1,x,mid);	
	}
}row[N],col[N];
int main(){
    //~ freopen("file.in", "r", stdin);
    int n,m,r,q,p;
    scanf("%d%d%d%d%d",&n,&m,&r,&q,&p);
    vector<vector<int> >arr(n+1,vector<int>(m+1));
    vector<vector<ll> >dp(n+1,vector<ll>(m+1));
    for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%d",&arr[i][j]);	
	for(int i=1;i<=n;i++){
		row[i].s.resize(m*4);
		for(int j=1;j<=m;j++)
			row[i].upd(j,arr[i][j],1,1,m);
	}		
	for(int i=1;i<=m;i++){
		col[i].s.resize(n*3);
		for(int j=1;j<=n;j++)
			col[i].upd(j,arr[j][i],1,1,n);
	}
	while(q--){
		char type;
		int p,x;
		scanf(" %c%d%d",&type,&p,&x);
		if(type=='N'){
			int pos=0;
			for(int i=0;i<r;i++){
				pos=col[p].getL(pos+1,n,x,1,1,n);
				if(pos==-1)
					break;
				arr[pos][p]--;
				col[p].upd(pos,arr[pos][p],1,1,n);
			}
		}
		else if(type=='S'){
			int pos=n+1;
			for(int i=0;i<r;i++){
				pos=col[p].getR(1,pos-1,x,1,1,n);
				if(pos==-1)
					break;
				arr[pos][p]--;
				col[p].upd(pos,arr[pos][p],1,1,n);
			}
		}
		else if(type=='W'){
			int pos=0;
			for(int i=0;i<r;i++){
				pos=row[p].getL(pos+1,m,x,1,1,m);
				if(pos==-1)
					break;
				arr[p][pos]--;
				row[p].upd(pos,arr[p][pos],1,1,m);
			}
		}
		else{
			int pos=m+1;
			for(int i=0;i<r;i++){
				pos=row[p].getR(1,pos-1,x,1,1,m);
				if(pos==-1)
					break;
				arr[p][pos]--;
				row[p].upd(pos,arr[p][pos],1,1,m);
			}
		}
	}		
	ll ans=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			dp[i][j]=arr[i][j]+dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]; 	
			if(min(i,j)>=p)
				umax(ans,dp[i][j]-dp[i][j-p]-dp[i-p][j]+dp[i-p][j-p]);
		}		
	printf("%lld\n",ans);	
	return 0;
}

Compilation message

ufo.cpp: In function 'int main()':
ufo.cpp:61:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d%d",&n,&m,&r,&q,&p);
                                       ^
ufo.cpp:66:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&arr[i][j]); 
                          ^
ufo.cpp:80:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c%d%d",&type,&p,&x);
                               ^

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 48904 KB Output is correct
2 Correct 23 ms 48904 KB Output is correct
3 Correct 16 ms 49036 KB Output is correct
4 Correct 33 ms 49300 KB Output is correct
5 Correct 69 ms 50992 KB Output is correct
6 Correct 219 ms 68212 KB Output is correct
7 Correct 366 ms 90020 KB Output is correct
8 Correct 326 ms 90020 KB Output is correct
9 Correct 469 ms 89472 KB Output is correct
10 Correct 663 ms 90020 KB Output is correct
11 Correct 493 ms 89820 KB Output is correct
12 Correct 676 ms 90020 KB Output is correct
13 Correct 766 ms 98180 KB Output is correct
14 Correct 636 ms 89820 KB Output is correct
15 Correct 703 ms 90020 KB Output is correct
16 Correct 389 ms 89820 KB Output is correct
17 Correct 989 ms 98180 KB Output is correct
18 Correct 439 ms 94356 KB Output is correct
19 Correct 456 ms 94208 KB Output is correct
20 Correct 1216 ms 119264 KB Output is correct