Submission #188605

#	Time	Username	Problem	Language	Result	Execution time	Memory
188605		knon0501	조개 줍기 (KOI17_shell)	C++14	100 / 100	1146 ms	53692 KiB

shell

#include <bits/stdc++.h>
using namespace std;
int n,nn;
int seg[1501][6000];
int a[1501][1501];
int dp[1501][1501];
inline int f(int y,int x){
    int ret=0;
    for(int i=nn+x-1 ; i>=1 ; i/=2)ret+=seg[y][i];
    return ret;
}
void upd(int y,int l,int r,int lef,int rig,int lev,int k){
    if(l<=lef && rig<=r){
        seg[y][lev]+=k;
        return;
    }
    if(r<lef || l>rig)return;
    int mid=(lef+rig)/2;
    upd(y,l,r,lef,mid,lev*2,k);
    upd(y,l,r,mid+1,rig,lev*2+1,k);
}
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cin>>n;
    int i,j;

    for(i=1 ; i<=n ; i++)for(j=1 ; j<=n ; j++)cin>>a[i][j];
    for(i=1 ; i<=n ; i++)for(j=1 ; j<=n ; j++)dp[i][j]=max(dp[i-1][j],dp[i][j-1])+a[i][j];

    for(nn=1 ; nn<n ; nn*=2);
    long long ans=0;

    for(i=1 ; i<=n ; i++)
        for(j=1 ; j<=n ; j++)
            seg[i][nn+j-1]=dp[i][j],ans+=dp[i][j];

    cout<<ans<<"\n";
    for(i=1 ; i<=n ; i++){
        char c;
        int y,x;
        int k=1;
        cin>>c>>y>>x;
        if(c=='U')a[y][x]++;
        else{
            k=-1;
            a[y][x]--;
        }
        int l=x;
        int r=x;
        dp[y][x]=f(y,x)+k;
        for(j=x+1 ; j<=n ; j++){
            if(max(f(y-1,j),dp[y][j-1])+a[y][j]!=f(y,j)){
                dp[y][j]=f(y,j)+k;
                r=j;
            }
            else
                break;
        }
        r++;
        ans+=(r-l)*k;
        upd(y,l,r-1,1,nn,1,k);
        for(j=y+1 ; j<=n ; j++){
            while(l<=n && max(f(j,l-1),f(j-1,l))+a[j][l]==f(j,l))l++;
            if(l>n)break;
            dp[j][r-1]=f(j,r-1)+k;
            while(r<=n && max(dp[j][r-1],f(j-1,r))+a[j][r]!=f(j,r)){
                dp[j][r]=f(j,r)+k;
                r++;
            }
            ans+=(r-l)*k;
            upd(j,l,r-1,1,nn,1,k);

        }
        cout<<ans<<"\n";
    }
    return 0;
}

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