oj.uz

Submission #936056

# Submission time Handle Problem Language Result Execution time Memory
936056 2024-03-01T05:29:02 Z noyancanturk Nafta (COI15_nafta) C++17
100 / 100
 144 ms 80720 KB 
    #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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16984 KB Output is correct
2 Correct 3 ms 16848 KB Output is correct
3 Correct 2 ms 16988 KB Output is correct
4 Correct 2 ms 16732 KB Output is correct
5 Correct 2 ms 16772 KB Output is correct
6 Correct 3 ms 16732 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16984 KB Output is correct
2 Correct 3 ms 16848 KB Output is correct
3 Correct 2 ms 16988 KB Output is correct
4 Correct 2 ms 16732 KB Output is correct
5 Correct 2 ms 16772 KB Output is correct
6 Correct 3 ms 16732 KB Output is correct
7 Correct 5 ms 23132 KB Output is correct
8 Correct 6 ms 23132 KB Output is correct
9 Correct 5 ms 21596 KB Output is correct
10 Correct 4 ms 23216 KB Output is correct
11 Correct 4 ms 21084 KB Output is correct
12 Correct 4 ms 21084 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16984 KB Output is correct
2 Correct 3 ms 16848 KB Output is correct
3 Correct 2 ms 16988 KB Output is correct
4 Correct 2 ms 16732 KB Output is correct
5 Correct 2 ms 16772 KB Output is correct
6 Correct 3 ms 16732 KB Output is correct
7 Correct 5 ms 23132 KB Output is correct
8 Correct 6 ms 23132 KB Output is correct
9 Correct 5 ms 21596 KB Output is correct
10 Correct 4 ms 23216 KB Output is correct
11 Correct 4 ms 21084 KB Output is correct
12 Correct 4 ms 21084 KB Output is correct
13 Correct 91 ms 67168 KB Output is correct
14 Correct 121 ms 63000 KB Output is correct
15 Correct 144 ms 80720 KB Output is correct
16 Correct 73 ms 62936 KB Output is correct
17 Correct 54 ms 63024 KB Output is correct
18 Correct 55 ms 62976 KB Output is correct