oj.uz

Submission #931069

# Submission time Handle Problem Language Result Execution time Memory
931069 2024-02-21T07:45:42 Z noyancanturk Nafta (COI15_nafta) C++17
100 / 100
 177 ms 76404 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>;

string s[lim];

int n,m,gn=0;
bool vis[lim*lim];
int parent[lim*lim];
vector<int>val,ll,rr;

inline void dfs(int node,int par){
    vis[node]=1;
    int x=node/lim,y=node%lim;
    parent[node]=parent[par];
    val.back()+=s[x][y]-'0';
    ll.back()=min(ll.back(),y);
    rr.back()=max(rr.back(),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;
    if(r<l)return;
    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;
        }
    }
    dnc(l,mid-1,optl,opt);
    dnc(mid+1,r,opt,optr);
}

inline void solve(){
    cin>>n>>m;
    s[0]=s[n+1]=string(m+2,'.');
    for(int i=1;i<=n;i++){
        cin>>s[i];
        s[i]='.'+s[i]+'.';
    }
    for(int i=0;i<=n+1;i++){
        for(int j=0;j<=m+1;j++){
            if(s[i][j]=='.'){
                vis[P(i,j)]=1;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(!vis[P(i,j)]){
                parent[P(i,j)]=gn++;
                val.pb(0);
                ll.pb(INT_MAX);
                rr.pb(-1);
                dfs(P(i,j),-1);
            }
        }
    }
    int*lp=ll.data(),*rp=rr.data(),*valp=val.data();
    for(int i=0;i<gn;i++){
        g[lp[i]][0]+=valp[i];
        g[lp[i]][lp[i]]-=valp[i];
        g[rp[i]+1][0]-=valp[i];
        g[rp[i]+1][lp[i]]+=valp[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];
        }
    }
    for(int i=0;i<=m;i++){
        for(int j=0;j<=m;j++){
            dp[i][j]=INT_MIN;
        }
    }
    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,m,1,m);
        cout<<*max_element(dp[i]+i+1,dp[i]+m+1)<<"\n";
    }
}

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef Local  
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#else
    
#endif
    int t=1;
    //cin>>t;
    while (t--)
    {
        solve();
    }
}

Compilation message

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8796 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 1 ms 8796 KB Output is correct
5 Correct 2 ms 9048 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8796 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 1 ms 8796 KB Output is correct
5 Correct 2 ms 9048 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 4 ms 16220 KB Output is correct
8 Correct 5 ms 16220 KB Output is correct
9 Correct 5 ms 16476 KB Output is correct
10 Correct 4 ms 16220 KB Output is correct
11 Correct 3 ms 17240 KB Output is correct
12 Correct 4 ms 17244 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8796 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 1 ms 8796 KB Output is correct
5 Correct 2 ms 9048 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 4 ms 16220 KB Output is correct
8 Correct 5 ms 16220 KB Output is correct
9 Correct 5 ms 16476 KB Output is correct
10 Correct 4 ms 16220 KB Output is correct
11 Correct 3 ms 17240 KB Output is correct
12 Correct 4 ms 17244 KB Output is correct
13 Correct 110 ms 65836 KB Output is correct
14 Correct 134 ms 62928 KB Output is correct
15 Correct 177 ms 76404 KB Output is correct
16 Correct 92 ms 62508 KB Output is correct
17 Correct 69 ms 59732 KB Output is correct
18 Correct 70 ms 59624 KB Output is correct