#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 |
356 KB |
Output is correct |
| 3 |
Correct |
3 ms |
560 KB |
Output is correct |
| 4 |
Correct |
26 ms |
1032 KB |
Output is correct |
| 5 |
Correct |
164 ms |
3684 KB |
Output is correct |
| 6 |
Correct |
370 ms |
24088 KB |
Output is correct |
| 7 |
Correct |
583 ms |
58104 KB |
Output is correct |
| 8 |
Correct |
504 ms |
62564 KB |
Output is correct |
| 9 |
Correct |
978 ms |
62776 KB |
Output is correct |
| 10 |
Correct |
1277 ms |
69564 KB |
Output is correct |
| 11 |
Correct |
1031 ms |
72408 KB |
Output is correct |
| 12 |
Correct |
1343 ms |
76144 KB |
Output is correct |
| 13 |
Correct |
1533 ms |
91280 KB |
Output is correct |
| 14 |
Correct |
1131 ms |
91280 KB |
Output is correct |
| 15 |
Correct |
1294 ms |
91280 KB |
Output is correct |
| 16 |
Correct |
567 ms |
93988 KB |
Output is correct |
| 17 |
Correct |
1797 ms |
113744 KB |
Output is correct |
| 18 |
Correct |
481 ms |
115020 KB |
Output is correct |
| 19 |
Correct |
832 ms |
119888 KB |
Output is correct |
| 20 |
Execution timed out |
2037 ms |
174632 KB |
Time limit exceeded |
