Submission #1103478

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103478		doducanh	Nafta (COI15_nafta)	C++14	100 / 100	224 ms	106920 KiB

nafta

///breaker
#pragma GCC optimize("O2")
#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=rl;i<=min(m-1,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[maxx][k]+=tmp;
            }
        }
    }
    for(int i=0;i<=m+1;i++){
        for(int j=0;j<=m+1;j++){
            w[i][j]=0;
            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+1,0,m+1);
        for(int j=0;j<=m+1;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;
}
/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH
 */

Compilation message (stderr)

nafta.cpp: In function 'void dvc(long long int, long long int, long long int, long long int, long long int)':
nafta.cpp:44:8: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   44 |     dvc(lvl,l,m-1,rl,pos);
      |     ~~~^~~~~~~~~~~~~~~~~~

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