답안 #40632

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
40632 2018-02-06T01:28:38 Z faustaadp UFO (IZhO14_ufo) C++11
100 / 100
1994 ms 102448 KB
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
int n,m,r,k,p,i,j,ta,tb,hv,L,R,C,hs;
char ct;
vector<vector<int> > a,str,stc,pr; 
pair<int,int> hz;
void ini()
{
	for(i=0;i<=n;i++)
	{
		vector<int> vt;
		for(j=0;j<=m;j++)
			vt.pb(0);
		a.pb(vt);
	}
	for(i=0;i<=n;i++)
	{
		vector<int> vt;
		for(j=0;j<=m;j++)
			vt.pb(0);
		pr.pb(vt);
	}
	for(i=0;i<=n;i++)
	{
		vector<int> vt;
		for(j=0;j<=4*m;j++)
			vt.pb(0);
		stc.pb(vt);
	}
	for(i=0;i<=m;i++)
	{
		vector<int> vt;
		for(j=0;j<=4*n;j++)
			vt.pb(0);
		str.pb(vt);
	}
}
void upr(int aa,int bb,int cc,int dd,int ee,int ff)
{
	if(aa==bb)
		str[ff][ee]=dd;
	else
	{
		int ce=(aa+bb)/2;
		if(cc<=ce)
			upr(aa,ce,cc,dd,ee*2,ff);
		else
			upr(ce+1,bb,cc,dd,ee*2+1,ff);
		str[ff][ee]=max(str[ff][ee*2],str[ff][ee*2+1]);
	}		
}
void upc(int aa,int bb,int cc,int dd,int ee,int ff)
{
	if(aa==bb)
		stc[ff][ee]=dd;
	else
	{
		int ce=(aa+bb)/2;
		if(cc<=ce)
			upc(aa,ce,cc,dd,ee*2,ff);
		else
			upc(ce+1,bb,cc,dd,ee*2+1,ff);
		stc[ff][ee]=max(stc[ff][ee*2],stc[ff][ee*2+1]);
	}		
}
pair<int,int> nilN(int aa,int bb,int ee,int ff)
{
	if(aa==bb)
		return mp(aa,str[ff][ee]-1);
	int ce=(aa+bb)/2;
	if(str[ff][ee*2]>=tb)
		return nilN(aa,ce,ee*2,ff);
	else
		return nilN(ce+1,bb,ee*2+1,ff);
}
pair<int,int> nilS(int aa,int bb,int ee,int ff)
{
	if(aa==bb)
		return mp(aa,str[ff][ee]-1);
	int ce=(aa+bb)/2;
	if(str[ff][ee*2+1]>=tb)
		return nilS(ce+1,bb,ee*2+1,ff);
	else
		return nilS(aa,ce,ee*2,ff);
}
pair<int,int> nilW(int aa,int bb,int ee,int ff)
{
	if(aa==bb)
		return mp(aa,stc[ff][ee]-1);
	int ce=(aa+bb)/2;
	if(stc[ff][ee*2]>=tb)
		return nilW(aa,ce,ee*2,ff);
	else
		return nilW(ce+1,bb,ee*2+1,ff);
}
pair<int,int> nilE(int aa,int bb,int ee,int ff)
{
	if(aa==bb)
		return mp(aa,stc[ff][ee]-1);
	int ce=(aa+bb)/2;
	if(stc[ff][ee*2+1]>=tb)
		return nilE(ce+1,bb,ee*2+1,ff);
	else
		return nilE(aa,ce,ee*2,ff);
}
int nil(int aa,int bb,int cc,int ee,int ff)
{
	if(aa==bb)
		return stc[ff][ee];
	else
	{
		int ce=(aa+bb)/2;
		if(cc<=ce)
			return nil(aa,ce,cc,ee*2,ff);
		else
			return nil(ce+1,bb,cc,ee*2+1,ff);
	}
}
int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m>>r>>k>>p;
	ini();
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
		{
			cin>>ta;
			upr(1,n,i,ta,1,j);
			upc(1,m,j,ta,1,i);
		}
	while(k--)
	{
		cin>>ct>>ta>>tb;
		vector<pair<int,int> > v;
		if(ct=='N')
		{
			for(i=1;i<=r;i++)
			{
				if(str[ta][1]<tb)
					break;
				hz=nilN(1,n,1,ta);
				upr(1,n,hz.fi,-10e8,1,ta);
				v.pb(hz);
			}
			for(i=0;i<v.size();i++)
			{
				upr(1,n,v[i].fi,v[i].se,1,ta);
				upc(1,m,ta,v[i].se,1,v[i].fi);
			}
		}
		else
		if(ct=='S')
		{
			for(i=1;i<=r;i++)
			{
				if(str[ta][1]<tb)
					break;
				hz=nilS(1,n,1,ta);
				upr(1,n,hz.fi,-10e8,1,ta);
				v.pb(hz);
			}
			for(i=0;i<v.size();i++)
			{
				upr(1,n,v[i].fi,v[i].se,1,ta);
				upc(1,m,ta,v[i].se,1,v[i].fi);
			}
		}
		else
		if(ct=='W')
		{
			for(i=1;i<=r;i++)
			{
				if(stc[ta][1]<tb)
					break;
				hz=nilW(1,m,1,ta);
				upc(1,m,hz.fi,-10e8,1,ta);
				v.pb(hz);
			}
			for(i=0;i<v.size();i++)
			{
				upr(1,n,ta,v[i].se,1,v[i].fi);
				upc(1,m,v[i].fi,v[i].se,1,ta);
			}
		}
		else
		{
			for(i=1;i<=r;i++)
			{
				if(stc[ta][1]<tb)
					break;
				hz=nilE(1,m,1,ta);
				upc(1,m,hz.fi,-10e8,1,ta);
				v.pb(hz);
			}
			for(i=0;i<v.size();i++)
			{
				upr(1,n,ta,v[i].se,1,v[i].fi);
				upc(1,m,v[i].fi,v[i].se,1,ta);
			}
		}
	}
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			a[i][j]=nil(1,m,j,1,i);
			pr[i][j]=pr[i][j-1]+pr[i-1][j]-pr[i-1][j-1]+a[i][j];
	//		cout<<a[i][j]<<" ";
		}
	//	cout<<"\n";
	}
	for(i=1;i+p-1<=n;i++)
		for(j=1;j+p-1<=m;j++)
			hs=max(hs,pr[i+p-1][j+p-1]-pr[i-1][j+p-1]-pr[i+p-1][j-1]+pr[i-1][j-1]);
	cout<<hs<<"\n";
}

Compilation message

ufo.cpp: In function 'int main()':
ufo.cpp:150:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(i=0;i<v.size();i++)
             ^
ufo.cpp:167:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(i=0;i<v.size();i++)
             ^
ufo.cpp:184:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(i=0;i<v.size();i++)
             ^
ufo.cpp:200:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(i=0;i<v.size();i++)
             ^
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 352 KB Output is correct
3 Correct 3 ms 552 KB Output is correct
4 Correct 30 ms 824 KB Output is correct
5 Correct 159 ms 2868 KB Output is correct
6 Correct 368 ms 19772 KB Output is correct
7 Correct 570 ms 46016 KB Output is correct
8 Correct 501 ms 46016 KB Output is correct
9 Correct 959 ms 46016 KB Output is correct
10 Correct 1233 ms 46016 KB Output is correct
11 Correct 905 ms 46016 KB Output is correct
12 Correct 1251 ms 46016 KB Output is correct
13 Correct 1401 ms 56696 KB Output is correct
14 Correct 1093 ms 56696 KB Output is correct
15 Correct 1228 ms 56696 KB Output is correct
16 Correct 505 ms 56696 KB Output is correct
17 Correct 1769 ms 56696 KB Output is correct
18 Correct 450 ms 56696 KB Output is correct
19 Correct 752 ms 56696 KB Output is correct
20 Correct 1994 ms 102448 KB Output is correct