Submission #1128921

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128921		viet123@	Nafta (COI15_nafta)	C++20	100 / 100	301 ms	79712 KiB

nafta

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define fi first
#define se second
#define ii pair<int,int>
#define mp make_pair
#define in(x) freopen(x,"r",stdin)
#define out(x) freopen(x,"w",stdout)
#define bit(x,i) ((x>>i)&1)
#define lc (id<<1)
#define rc ((id<<1)^1)
const int maxn=2e3+7;
const int inf=1e9+7;
int dx[4]={1,0,0,-1};
int dy[4]={0,-1,1,0};
string s[maxn];
int val[maxn];
bool vst[maxn][maxn];
int w[maxn][maxn];
int I[maxn][maxn];
int dp[maxn][maxn];
int n,m;
bool check(int x,int y)
{
    return (1<=x&&x<=n&&1<=y&&y<=m&&vst[x][y]==0&&s[x][y]>='0'&&s[x][y]<='9');
}
void dvc(int lvl,int l,int r,int rl,int rr)
{
    if(l>r)return;
    int m=(l+r)/2;
    int best=-inf,pos;
    for(int i=max(rl,m+1);i<=rr;i++){
        int tmp=dp[lvl-1][i]+w[m][i];
        if(tmp>best){
            best=tmp;
            pos=i;
        }
    }
    dp[lvl][m]=best;
    dvc(lvl,l,m-1,rl,pos);
    dvc(lvl,m+1,r,pos,rr);
}
void sol(void){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        s[i]=" "+s[i];
    }
    for(int i=1;i<=m;i++){
        for(int j=0;j<=m;j++){
            dp[i][j]=-inf;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(!check(i,j))continue;
            queue<ii>q;
            q.push({i,j});
            int minn=j;
            int maxx=j;
            int tmp=0;
            vst[i][j]=1;
            while(q.size()){
                int x=q.front().fi;
                int y=q.front().se;
                tmp+=(s[x][y]-'0');
                minn=min(minn,y);
                maxx=max(maxx,y);
                q.pop();
                for(int k=0;k<4;k++){
                    int nx=x+dx[k];
                    int ny=y+dy[k];
                    if(!check(nx,ny))continue;
                    q.push({nx,ny});
                    vst[nx][ny]=1;
                }
            }
            for(int k=minn;k<=maxx;k++){
                I[minn][k]+=tmp;
            }
        }
    }
    for(int i=m;i>=0;i--){
        for(int j=1;j<=m;j++){
            w[i][j]=w[i+1][j]+I[i+1][j];
        }
    }
    dp[0][0]=0;
    int res=0;
    for(int i=1;i<=m;i++){
        dvc(i,0,m,0,m);
        
        for(int j=0;j<=m;j++){
            res=max(res,dp[i][j]);
        }
        cout<<res<<"\n";
    }
 
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    while(t--){
        sol();
    }
    // you should actually read the stuff at the bottom
    return 0;
}

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