oj.uz

Submission #931068

# Submission time Handle Problem Language Result Execution time Memory
931068 2024-02-21T07:40:56 Z noyancanturk Nafta (COI15_nafta) C++17
100 / 100
 191 ms 150436 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;

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]=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]+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 10844 KB Output is correct
2 Correct 1 ms 8808 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 2 ms 10588 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 2 ms 10844 KB Output is correct
2 Correct 1 ms 8808 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 8 ms 20564 KB Output is correct
8 Correct 7 ms 20828 KB Output is correct
9 Correct 6 ms 22108 KB Output is correct
10 Correct 5 ms 21084 KB Output is correct
11 Correct 5 ms 22108 KB Output is correct
12 Correct 4 ms 18780 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 1 ms 8808 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 8 ms 20564 KB Output is correct
8 Correct 7 ms 20828 KB Output is correct
9 Correct 6 ms 22108 KB Output is correct
10 Correct 5 ms 21084 KB Output is correct
11 Correct 5 ms 22108 KB Output is correct
12 Correct 4 ms 18780 KB Output is correct
13 Correct 140 ms 127908 KB Output is correct
14 Correct 163 ms 126732 KB Output is correct
15 Correct 191 ms 150436 KB Output is correct
16 Correct 120 ms 121888 KB Output is correct
17 Correct 88 ms 116576 KB Output is correct
18 Correct 90 ms 116044 KB Output is correct