Submission #1147351

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147351		Warinchai	Nafta (COI15_nafta)	C++20	100 / 100	209 ms	87476 KiB

nafta

#include<bits/stdc++.h>
using namespace std;
string ar[2005];
int vis[2005][2005];
int sum[2005][2005];
int temp[2005];
int dp[2005][2005];
int R,S;
int l,r;
vector<pair<int,int>>v[2005];
int val=0;
void dfs(int x,int y){
    if(x>=R||x<0||y>=S||y<0||ar[x][y]=='.'||vis[x][y])return;
    vis[x][y]=1;
    val+=ar[x][y]-'0';
    l=min(y,l);
    r=max(y,r);
    dfs(x,y+1),dfs(x,y-1),dfs(x+1,y),dfs(x-1,y);
}
int get(int l,int r){
    return sum[l][r]-sum[r+1][r+1];
}
void solve(int st,int en,int l,int r,int lv){
    if(st>en)return;
    int m=(st+en)/2;
    //cerr<<"m:"<<m<<" "<<l<<" "<<r<<"\n";
    pair<int,int>ans={0,0};
    for(int i=l;i<=min(m,r);i++){
        ans=max(ans,{dp[lv-1][i-1]+get(i,m),i});
    }
    //cerr<<"ans:"<<ans.first<<" "<<ans.second<<"\n";
    dp[lv][m]=ans.first;
    solve(st,m-1,l,ans.second,lv);
    solve(m+1,en,ans.second,r,lv);
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>R>>S;
    for(int i=0;i<R;i++)cin>>ar[i];
    for(int i=0;i<R;i++){
        for(int j=0;j<S;j++){
            if(ar[i][j]=='.'||vis[i][j])continue;
            val=0;
            l=j,r=j;
            dfs(i,j);
            v[l+1].push_back({r+1,val});
            //cerr<<"range:"<<l+1<<" "<<r+1<<" "<<val<<"\n";
        }
    }
    //cerr<<"sum:\n";
    for(int i=S;i>0;i--){
        for(auto [x,val]:v[i])temp[x]+=val;
        for(int j=S;j>=i;j--)sum[i][j]=sum[i][j+1]+temp[j];
        //cerr<<"\n";
    }
    for(int i=1;i<=S;i++){
        //cerr<<"LV:"<<i<<"\n";
        solve(i,S,i,S,i);
        //cerr<<"\n";
        int ans=0;
        for(int j=i;j<=S;j++){
            ans=max(ans,dp[i][j]);
        }
        cout<<ans<<" ";
    }
}

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