| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 74477 |
2018-09-02T07:21:48 Z |
gs18115 |
None (KOI17_shell) |
C++14 |
|
903 ms |
146608 KB |
#include<iostream>
using namespace std;
typedef long long LL;
const LL MAXN=1510;
const LL n=2048;
LL FT[MAXN][n+10];
LL N;
void FI(const LL&i,LL j,const LL&dif)
{
if(i<=0||j<=0||i>N||j>N)
return;
for(;j<=n;j+=j&-j)
FT[i][j]+=dif;
return;
}
void FS(const LL&i,LL j,LL&SC)
{
SC=0;
if(i<=0||j<=0||i>N||j>N)
return;
for(;j>0;j=j&(j-1))
SC+=FT[i][j];
return;
}
LL arr[MAXN][MAXN];
LL dp[MAXN][MAXN];
LL S[MAXN],E[MAXN];
char C;
LL ch;
LL A,B;
LL i,j;
LL X,Y;
LL sx,ex,sy,ey;
LL flag;
bool flag1,flag2;
LL ans;
LL t1,t2,t3;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin>>N;
for(i=1;i<=N;i++)
for(j=1;j<=N;j++)
cin>>arr[i][j];
for(i=1;i<=N;i++)
{
for(j=1;j<=N;j++)
{
dp[i][j]=arr[i][j]+max(dp[i-1][j],dp[i][j-1]);
FI(i,j,dp[i][j]-dp[i][j-1]);
ans+=dp[i][j];
}
}
cout<<ans<<endl;
for(i=0;i<N;i++)
{
for(j=1;j<=N;j++)
{
S[j]=N+1;
E[j]=0;
}
cin>>C>>X>>Y;
ch=C=='U'?1LL:-1LL;
arr[X][Y]+=ch;
sx=ex=X;
sy=ey=Y;
S[X]=E[X]=Y;
flag=N;
flag1=flag2=true;
while(ex<=N&&(flag1||flag2))
{
if(flag1)
{
if(sy<N)
{
FS(sx,sy,t1);
FS(sx+1,sy,t2);
FS(sx+1,sy-1,t3);
if(t2!=max(t1+ch,t3)+arr[sx+1][sy])
S[++sx]=sy;
else if(sx!=ex)
sy++;
else
{
FS(sx,sy+1,t2);
FS(sx-1,sy+1,t3);
if(t2!=max(t1+ch,t3)+arr[sx][sy+1])
sy++;
else
{
flag=sx;
flag1=false;
}
}
}
else
{
FS(sx,sy,t1);
FS(sx+1,sy,t2);
FS(sx+1,sy-1,t3);
if(t2!=max(t1+ch,t3)+arr[sx+1][sy])
S[++sx]=sy;
else
{
flag=sx;
flag1=false;
}
}
}
if(flag2)
{
if(ey<N)
{
FS(ex,ey,t1);
FS(ex,ey+1,t2);
FS(ex-1,ey+1,t3);
if(t2!=max(t1+ch,t3)+arr[ex][ey+1])
ey++;
else
{
E[ex]=ey;
if(ey>S[ex+1])
ex++;
else
{
FS(ex+1,ey,t2);
FS(ex+1,ey-1,t3);
if(t2!=max(t1+ch,t3)+arr[ex+1][ey])
ex++;
else
flag2=false;
}
}
}
else
{
E[ex]=ey;
if(ey>S[ex+1])
ex++;
else
{
FS(ex+1,ey,t2);
FS(ex+1,ey-1,t3);
if(t2!=max(t1+ch,t3)+arr[ex+1][ey])
ex++;
else
flag2=false;
}
}
}
S[sx]=min(S[sx],sy);
E[ex]=ey;
}
for(j=X;j<=flag;j++)
{
ans+=ch*(E[j]-S[j]+1);
FI(j,S[j],ch);
FI(j,E[j]+1,-ch);
}
cout<<ans<<'\n';
}
cout<<endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
2552 KB |
Output is correct |
| 2 |
Correct |
5 ms |
2556 KB |
Output is correct |
| 3 |
Correct |
5 ms |
2728 KB |
Output is correct |
| 4 |
Correct |
6 ms |
2728 KB |
Output is correct |
| 5 |
Correct |
6 ms |
2728 KB |
Output is correct |
| 6 |
Correct |
6 ms |
2728 KB |
Output is correct |
| 7 |
Correct |
5 ms |
2728 KB |
Output is correct |
| 8 |
Correct |
5 ms |
2728 KB |
Output is correct |
| 9 |
Correct |
5 ms |
2892 KB |
Output is correct |
| 10 |
Correct |
5 ms |
2892 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
286 ms |
60216 KB |
Output is correct |
| 2 |
Correct |
237 ms |
60384 KB |
Output is correct |
| 3 |
Correct |
250 ms |
60384 KB |
Output is correct |
| 4 |
Correct |
253 ms |
60384 KB |
Output is correct |
| 5 |
Correct |
249 ms |
60384 KB |
Output is correct |
| 6 |
Correct |
271 ms |
60384 KB |
Output is correct |
| 7 |
Correct |
236 ms |
60384 KB |
Output is correct |
| 8 |
Correct |
228 ms |
60384 KB |
Output is correct |
| 9 |
Correct |
229 ms |
60384 KB |
Output is correct |
| 10 |
Correct |
228 ms |
60448 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
2552 KB |
Output is correct |
| 2 |
Correct |
5 ms |
2556 KB |
Output is correct |
| 3 |
Correct |
5 ms |
2728 KB |
Output is correct |
| 4 |
Correct |
6 ms |
2728 KB |
Output is correct |
| 5 |
Correct |
6 ms |
2728 KB |
Output is correct |
| 6 |
Correct |
6 ms |
2728 KB |
Output is correct |
| 7 |
Correct |
5 ms |
2728 KB |
Output is correct |
| 8 |
Correct |
5 ms |
2728 KB |
Output is correct |
| 9 |
Correct |
5 ms |
2892 KB |
Output is correct |
| 10 |
Correct |
286 ms |
60216 KB |
Output is correct |
| 11 |
Correct |
237 ms |
60384 KB |
Output is correct |
| 12 |
Correct |
250 ms |
60384 KB |
Output is correct |
| 13 |
Correct |
253 ms |
60384 KB |
Output is correct |
| 14 |
Correct |
249 ms |
60384 KB |
Output is correct |
| 15 |
Correct |
271 ms |
60384 KB |
Output is correct |
| 16 |
Correct |
236 ms |
60384 KB |
Output is correct |
| 17 |
Correct |
228 ms |
60384 KB |
Output is correct |
| 18 |
Correct |
229 ms |
60384 KB |
Output is correct |
| 19 |
Correct |
228 ms |
60448 KB |
Output is correct |
| 20 |
Correct |
283 ms |
60448 KB |
Output is correct |
| 21 |
Correct |
276 ms |
60448 KB |
Output is correct |
| 22 |
Correct |
294 ms |
69024 KB |
Output is correct |
| 23 |
Correct |
835 ms |
77596 KB |
Output is correct |
| 24 |
Correct |
775 ms |
86172 KB |
Output is correct |
| 25 |
Correct |
790 ms |
94664 KB |
Output is correct |
| 26 |
Correct |
233 ms |
99188 KB |
Output is correct |
| 27 |
Correct |
238 ms |
103420 KB |
Output is correct |
| 28 |
Correct |
304 ms |
112108 KB |
Output is correct |
| 29 |
Correct |
298 ms |
120768 KB |
Output is correct |
| 30 |
Correct |
824 ms |
129300 KB |
Output is correct |
| 31 |
Correct |
903 ms |
138016 KB |
Output is correct |
| 32 |
Correct |
253 ms |
142296 KB |
Output is correct |
| 33 |
Correct |
213 ms |
146608 KB |
Output is correct |
| 34 |
Correct |
5 ms |
2892 KB |
Output is correct |
