Submission #74423

#	Time	Username	Problem	Language	Result	Execution time	Memory
74423		gs18115	조개 줍기 (KOI17_shell)	C++14	0 / 100	256 ms	58140 KiB

shell

#include<iostream>
using namespace std;
typedef long long LL;
const LL MAXN=1510;
const LL n=2048;
LL FT[MAXN][MAXN];
void FI(const LL&i,LL j,const LL&dif)
{
    if(j==0)
        return;
    for(;j<MAXN;j+=j&-j)
        FT[i][j]+=dif;
    return;
}
void FS(const LL&i,LL j,LL&SC)
{
    SC=0;
    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 A,B;
LL N;
LL i,j;
LL X,Y,x,y;
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++)
    {
        cin>>C>>X>>Y;
        C=C=='U'?1:-1;
        arr[X][Y]+=C;
        x=X;
        y=Y;
        S[x]=y;
        while(x<N)
        {
            if(y<N)
            {
                FS(x,y,t1);
                FS(x+1,y,t2);
                FS(x+1,y-1,t3);
                if(t2!=max(t1+C,t3)+arr[x+1][y])
                    S[++x]=y;
                else
                    y++;
            }
            else
                S[++x]=y;
        }
        x=X;
        y=Y;
        while(x<=N)
        {
            if(y<N)
            {
                FS(x,y,t1);
                FS(x,y+1,t2);
                FS(x-1,y+1,t3);
                if(t2!=max(t1+C,t3)+arr[x][y+1])
                    y++;
                else
                    E[x++]=y;
            }
            else
                E[x++]=y;
        }
        for(j=X;j<=N;j++)
        {
            ans+=C*(E[j]-S[j]+1);
            FI(j,S[j],C);
            FI(j,E[j]+1,-C);
        }
        cout<<ans<<'\n';
    }
    cout<<endl;
    return 0;
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 34
• Subtask 3: 0 / 54