Submission #404434

#	Time	Username	Problem	Language	Result	Execution time	Memory
404434		zaneyu	조개 줍기 (KOI17_shell)	C++14	100 / 100	653 ms	38452 KiB

shell

/*input
3

3 2 7

4 2 6

5 3 8

U 1 2

D 3 2

U 1 2
*/
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define MXTO(x,y) x=max(x,y)
#define pb push_back
#define f first
#define s second
#define ll long long
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define lowb(x) x&(-x)
const int maxn=1500+5;
int dp[maxn][maxn];
int arr[maxn][maxn];
int n;
ll ans=0;
void calc2(){
    REP1(i,n){
        REP1(j,n){
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])+arr[i][j];
            ans+=dp[i][j];
        }
    }
    cout<<ans<<'\n';
}
struct ft{
    ll bit[maxn];
    void upd(int p,int x){
        while(p<maxn){
            bit[p]+=x;
            p+=lowb(p);
        }
    }
    ll query(int p){
        ll ans=0;
        while(p){
            ans+=bit[p];
            p-=lowb(p);
        }
        return ans;
    }
    void upd(int l,int r,int x){
        upd(l,x);
        upd(r+1,-x);
    }
}bit[maxn];
map<pii,bool> changed;
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    cin>>n;
    REP1(i,n) REP1(j,n) cin>>arr[i][j];
    calc2();
    REP1(i,n) REP1(j,n) bit[i].upd(j,j,dp[i][j]);
    REP(i,n){
        char c;
        int x,y;
        cin>>c>>x>>y;
        int d=1;
        if(c=='D') d=-1;
        arr[x][y]+=d;
        int l=y,r=y;
        for(int i=x;i<=n;i++){
            while(l<r){
                dp[i][l]=max(bit[i].query(l-1),bit[i-1].query(l))+arr[i][l];
                if(bit[i].query(l)!=dp[i][l]) break;
                ++l;
            }
            bit[i].upd(l,n,d);
            while(r<=n){
                dp[i][r]=max(bit[i].query(r-1),bit[i-1].query(r))+arr[i][r];
                if(bit[i].query(r)-d==dp[i][r]) break;
                ++r;
            }
            bit[i].upd(r,n,-d);
            //cout<<l<<' '<<r<<'\n';
            ans+=d*(r-l);
        }
        changed.clear();
        cout<<ans<<'\n';
    }
}

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