oj.uz

Submission #931067

# Submission time Handle Problem Language Result Execution time Memory
931067 2024-02-21T07:38:34 Z noyancanturk Nafta (COI15_nafta) C++17
100 / 100
 224 ms 154696 KB 
#ifndef Local
    #pragma GCC optimize("O3,unroll-loops")
    const int lim=2e3+100;
#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;

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;

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]=LLONG_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]+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 'int64_t [4410000]' {aka 'long int [4410000]'} [-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 10840 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8792 KB Output is correct
4 Correct 3 ms 8796 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8792 KB Output is correct
4 Correct 3 ms 8796 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 7 ms 23896 KB Output is correct
8 Correct 7 ms 19036 KB Output is correct
9 Correct 8 ms 22364 KB Output is correct
10 Correct 7 ms 21592 KB Output is correct
11 Correct 5 ms 22108 KB Output is correct
12 Correct 5 ms 20060 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8792 KB Output is correct
4 Correct 3 ms 8796 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 7 ms 23896 KB Output is correct
8 Correct 7 ms 19036 KB Output is correct
9 Correct 8 ms 22364 KB Output is correct
10 Correct 7 ms 21592 KB Output is correct
11 Correct 5 ms 22108 KB Output is correct
12 Correct 5 ms 20060 KB Output is correct
13 Correct 141 ms 132444 KB Output is correct
14 Correct 168 ms 131104 KB Output is correct
15 Correct 224 ms 154696 KB Output is correct
16 Correct 112 ms 126144 KB Output is correct
17 Correct 88 ms 120488 KB Output is correct
18 Correct 89 ms 119972 KB Output is correct