Submission #936056

#	Time	Username	Problem	Language	Result	Execution time	Memory
936056		noyancanturk	Nafta (COI15_nafta)	C++17	100 / 100	144 ms	80720 KiB

nafta

    #ifndef Local
        #pragma GCC optimize("O3,unroll-loops")
        const int lim=2e3+5;
    #else
        const int lim=1e3+3;
    #endif
        
    #include "bits/stdc++.h"
    using namespace std;
        
    //#define int int64_t
    #define pb push_back
        
    int mod=1e9+7;
    //const int mod=(1ll<<61)-1;
        
    using pii=pair<int,int>;
        
    char s[lim][lim];
        
    int n,m,gn=0;
    bool vis[lim*lim];
    int parent[lim*lim];
    int val[lim*lim/2],ll[lim*lim/2],rr[lim*lim/2];
        
    inline void dfs(int node,int par){
        vis[node]=1;
        int x=node/lim,y=node%lim;
        parent[node]=parent[par];
        val[gn]+=s[x][y]-'0';
        ll[gn]=min(ll[gn],y);
        rr[gn]=max(rr[gn],y);
        for(int dd:{1,-1,lim,-lim}){
            if(!vis[node+dd]){
                dfs(node+dd,node);
            }
        }
    }
        
    #define P(i,j) ((i)*lim+(j))
        
    int g[lim][lim];
        
    int dp[lim][lim],curl;
        
    inline void dnc(int l,int r,int optl,int optr){
        int mid=(l+r)>>1;
        int opt=min(optr,mid-1);
        dp[curl][mid]=g[mid][opt]+dp[curl-1][opt];
        for(int i=opt;optl<=i;i--){
            if(dp[curl][mid]<g[mid][i]+dp[curl-1][i]){
                dp[curl][mid]=g[mid][i]+dp[curl-1][i];
                opt=i;
            }
        }
        if(l<=mid-1)dnc(l,mid-1,optl,opt);
        if(mid+1<=r)dnc(mid+1,r,opt,optr);
    }
    struct inpout{
        static const int sz=1<<16;
        char inp[sz];
        int curc=0,len=0;
        inline char gc(){
            if(curc==len){
                len=(int)fread(inp,1,sz,stdin);
                curc=0;
                if(!len)return -1;
            }
            return inp[curc++];
        }
        inline void readstr(char*c,int ll){
            for(int i=0;i<ll;i++){
                c[i]=gc();
            }
            gc();
        }
        inline int readint(){
            char c=gc();
            bool isneg=(c=='-');
            int ans=0;
            if(!isneg)ans=c-'0';
            c=gc();
            while('0'<=c&&c<='9'){
                ans=10*ans+c-'0';
                c=gc();
            }
            if(isneg)return -ans;
            return ans;
        }
        char out[sz];
        int curind=0;
        inline void flush(){
            fwrite(out,1,curind,stdout);
            curind=0;
        }
        inline void putchar(char c){
            out[curind++]=c;
            if(curind==sz)flush();
        }
        char temp[10];
        inline void putint(int i){
            int lll=0;
            while(i){
                temp[lll++]=(i%10)+'0';
                i/=10;
            }
            while(lll){
                putchar(temp[--lll]);
            }
            putchar('\n');
        }
    }io;
    inline void solve(){
        n=io.readint(),m=io.readint();
        for(int i=0;i<m+2;i++){
            s[0][i]=s[n+1][i]='.';
            vis[P(0,i)]=vis[P(n+1,i)]=1;
        }
        for(int i=1;i<=n;i++){
            vis[P(i,0)]=vis[P(i,m+1)]=1;
            for(int j=1;j<=m;j++){
                if((s[i][j]=io.gc())=='.'){
                    vis[P(i,j)]=1;
                }
            }
            io.gc();
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(!vis[P(i,j)]){
                    val[gn]=0;
                    ll[gn]=INT_MAX;
                    rr[gn]=-1;
                    parent[P(i,j)]=gn;
                    dfs(P(i,j),-1);
                    gn++;
                }
            }
        }
        for(int i=0;i<gn;i++){
            g[ll[i]][0]+=val[i];
            g[ll[i]][ll[i]]-=val[i];
            g[rr[i]+1][0]-=val[i];
            g[rr[i]+1][ll[i]]+=val[i];
        }
        for(int i=0;i<=m;i++){
            for(int j=1;j<=m;j++){
                g[i][j]+=g[i][j-1];
            }
        }
        for(int i=0;i<=m;i++){
            for(int j=1;j<=m;j++){
                g[j][i]+=g[j-1][i];
            }
        }
        dp[0][0]=0;
        for(int i=1;i<=m;i++){
            dp[0][i]=g[i][0];
        }
        cout<<*max_element(dp[0]+1,dp[0]+m+1)<<"\n";
        for(int i=1;i<m;i++){
            curl=i;
            dnc(i+1,m,i,m);
            cout<<*max_element(dp[i]+i+1,dp[i]+m+1)<<"\n";
        }
    }
        
    signed main(){
    #ifdef Local  
        freopen(".in","r",stdin);
        freopen(".out","w",stdout);
    #endif
        solve();
    }

Compilation message (stderr)

nafta.cpp: In function 'void solve()':
nafta.cpp:29:32: warning: array subscript -1 is below array bounds of 'int [4020025]' [-Warray-bounds]
   29 |         parent[node]=parent[par];
      |                      ~~~~~~~~~~^
nafta.cpp:23:9: note: while referencing 'parent'
   23 |     int parent[lim*lim];
      |         ^~~~~~

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