제출 #1128809

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1128809		vietvva@	Nafta (COI15_nafta)	C++20	34 / 100	1097 ms	43044 KiB

nafta

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ff first
#define ss second
#define For(i,a,b) for(int i = (a),_b = (b);i<=_b;i++)
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
const int N = 2100;
int n,m,k,q,x,y,z;
int a[N][N];
bool kt[N][N];
ll value[N],dp[N],ans[N];
struct modau{
    int l,r;
    ll w;
};
vector<modau> mo;
int o[] = {-1,0,1,0};
int p[] = {0,1,0,-1};
bool inGrid(int x,int y){
    return x>=1&&x<=n&&y>=1&&y<=m;
}
modau bfs(int s,int t){
    int l =t,r=t;
    ll sum = 0;
    queue<pii> q;
    q.push({s,t});
    kt[s][t]=true;
    while(!q.empty()){
        int u = q.front().ff;
        int v = q.front().ss;
        q.pop();
        sum+=a[u][v];
        l = min(l,v);
        r = max(r,v);
        For(i,0,3){
            int x = u + o[i];
            int y = v + p[i];
            if(!inGrid(x,y)||kt[x][y]||a[x][y]==-1) continue;
            kt[x][y]=true;
            q.push({x,y});
        }
    }
    return {l,r,sum};
}
void sweepline(){
    for(modau &v:mo) value[v.l]+=v.w,value[v.r+1]-=v.w;
    For(i,2,m) value[i] += value[i-1];
}
struct segmentree{
    int ans[4*N],du[4*N];
    int n;
    void buildseg(int x,int L,int R){
        du[x] = 0;
        if(L==R){
            ans[x] = dp[L];
            return;
        }
        int mid = (L+R)>>1;
        buildseg(x<<1,L,mid);
        buildseg(x<<1|1,mid+1,R);
        ans[x] = max(ans[x<<1],ans[x<<1|1]);
    }
    void build(int _n){
        n = _n;
        buildseg(1,1,n);
    }
    void get(int x){
        if(du[x]==0) return;
        du[x<<1]+=du[x];
        du[x<<1|1]+=du[x];
        ans[x<<1] += du[x];
        ans[x<<1|1] += du[x];
        du[x] = 0;
    }
    void update(int x,int L,int R,int i,int j,ll w){
        if(L>j||i>R) return ;
        if(i<=L&&R<=j){
            ans[x]+=w;
            du[x]+=w;
            return;
        }
        int mid = (L+R)>>1;
        get(x);
        update(x<<1,L,mid,i,j,w);
        update(x<<1|1,mid+1,R,i,j,w);
        ans[x] = max(ans[x<<1],ans[x<<1|1]);
    }
    ll ry(int x,int L,int R,int i,int j){
       if(L>j||i>R) return 0;
       if(i<=L&&R<=j) return ans[x];
       int mid =(L+R)>>1;
       get(x);
       return max(ry(x<<1,L,mid,i,j),ry(x<<1|1,mid+1,R,i,j));
    }
    void up(int i,int j,int w){
        update(1,1,n,i,j,w);
    }
    ll query(int i,int j){
        return ry(1,1,n,i,j);
    }
} seg;
vector<pii> add[N],Erase[N];
void solve(){
    for(modau &v:mo){
        add[v.l].pb({v.r,v.w});
        Erase[v.r+1].pb({v.l,v.w});
    }
    For(i,1,m) dp[i] = value[i];
    ans[1] = *max_element(&dp[1],&dp[m+1]);
    For(i,2,m){
        seg.build(m);
        For(j,1,m){
            for(pii &v:Erase[j]){
                seg.up(v.ff,j-1,v.ss);
            }
            dp[j] = value[j]+seg.query(1,j-1);
            for(pii &v:add[j]){
                seg.up(j,v.ff,-v.ss);
            }
        }
        ans[i] = *max_element(&dp[1],&dp[m+1]);
    }
}
void enter(){
    cin >> n >> m;
    For(i,1,n) For(j,1,m){
        char x;
        cin >> x;
        if(x=='.') a[i][j] = -1;
        else a[i][j] = x-'0';
    }
    For(i,1,n) For(j,1,m) if(!kt[i][j]&&a[i][j]!=-1) mo.pb(bfs(i,j));
    sweepline();
    solve();
    For(i,1,m) cout << ans[i]<<'\n';

}
int main(){
    #define task "DRILL"
    enter();
}

• Subtask 1: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 0 / 66