oj.uz

Submission #935959

# Submission time Handle Problem Language Result Execution time Memory
935959 2024-02-29T20:00:54 Z noyancanturk Nafta (COI15_nafta) C++17
100 / 100
 208 ms 68176 KB 
#ifndef Local
    #pragma GCC optimize("O3,unroll-loops")
    const int lim=(1<<11);
#else
    const int lim=(1<<11);
#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>>11,y=node&(2047);
    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)<<11)|(j))
    
int g[lim][lim];
    
int dp[2][lim],curl;
int ansss=INT_MIN;
    
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][opt];
    for(int i=opt;optl<=i;i--){
        if(dp[curl][mid]<g[mid][i]+dp[!curl][i]){
            dp[curl][mid]=g[mid][i]+dp[!curl][i];
            opt=i;
        }
    }
    ansss=max(ansss,dp[curl][mid]);
    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;
    }
}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];
        ansss=max(ansss,dp[0][i]);
    }
    cout<<ansss<<"\n";
    for(int i=1;i<m;i++){
        ansss=INT_MIN;
        curl=i&1;
        dnc(i,m,1,m);
        cout<<ansss<<"\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:28: warning: array subscript -1 is below array bounds of 'int [4194304]' [-Warray-bounds]
   29 |     parent[node]=parent[par];
      |                  ~~~~~~~~~~^
nafta.cpp:23:5: note: while referencing 'parent'
   23 | int parent[lim*lim];
      |     ^~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 18780 KB Output is correct
2 Correct 2 ms 18900 KB Output is correct
3 Correct 2 ms 18776 KB Output is correct
4 Correct 2 ms 18780 KB Output is correct
5 Correct 3 ms 18780 KB Output is correct
6 Correct 2 ms 18780 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 18780 KB Output is correct
2 Correct 2 ms 18900 KB Output is correct
3 Correct 2 ms 18776 KB Output is correct
4 Correct 2 ms 18780 KB Output is correct
5 Correct 3 ms 18780 KB Output is correct
6 Correct 2 ms 18780 KB Output is correct
7 Correct 7 ms 23132 KB Output is correct
8 Correct 7 ms 23132 KB Output is correct
9 Correct 7 ms 23388 KB Output is correct
10 Correct 7 ms 23132 KB Output is correct
11 Correct 6 ms 23132 KB Output is correct
12 Correct 6 ms 23092 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 18780 KB Output is correct
2 Correct 2 ms 18900 KB Output is correct
3 Correct 2 ms 18776 KB Output is correct
4 Correct 2 ms 18780 KB Output is correct
5 Correct 3 ms 18780 KB Output is correct
6 Correct 2 ms 18780 KB Output is correct
7 Correct 7 ms 23132 KB Output is correct
8 Correct 7 ms 23132 KB Output is correct
9 Correct 7 ms 23388 KB Output is correct
10 Correct 7 ms 23132 KB Output is correct
11 Correct 6 ms 23132 KB Output is correct
12 Correct 6 ms 23092 KB Output is correct
13 Correct 170 ms 51760 KB Output is correct
14 Correct 190 ms 51536 KB Output is correct
15 Correct 208 ms 68176 KB Output is correct
16 Correct 147 ms 51544 KB Output is correct
17 Correct 125 ms 45512 KB Output is correct
18 Correct 125 ms 45592 KB Output is correct