Submission #936059

#	Time	Username	Problem	Language	Result	Execution time	Memory
936059		noyancanturk	Nafta (COI15_nafta)	C++17	100 / 100	145 ms	78676 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<<18;
    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:28: warning: array subscript -1 is below array bounds of 'int [4020025]' [-Warray-bounds]
   29 |     parent[node]=parent[par];
      |                  ~~~~~~~~~~^
nafta.cpp:23:5: note: while referencing 'parent'
   23 | int parent[lim*lim];
      |     ^~~~~~

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