oj.uz

Submission #108099

# Submission time Handle Problem Language Result Execution time Memory
108099 2019-04-27T10:19:25 Z igzi Nafta (COI15_nafta) C++17
0 / 100
 4 ms 1408 KB 
#include <bits/stdc++.h>
#define maxS 2005

using namespace std;

int a[maxS][maxS],s,r,l,d,i,j,p[maxS][maxS];
long long dp[maxS][maxS],t[maxS][maxS],w[maxS][maxS],len[maxS][maxS],sum;
char c;

void dfs(int n){
sum+=a[n/s][n%s];
a[n/s][n%s]=-1;
d=max(d,n%s);
l=min(l,n%s);
if(n+s<r*s && a[n/s+1][n%s]!=-1) dfs(n+s);
if(n%s+1<s && a[n/s][n%s+1]!=-1) dfs(n+1);
if(n-s>=0 && a[n/s-1][n%s]!=-1) dfs(n-s);
if(n%s>0 && a[n/s][n%s-1]!=-1) dfs(n-1);
}

void resi(int k,int l,int d,int x,int y){
if(l>d) return;
int m=(l+d)/2,tmp,i;
for(i=x;i<min(m,y+1);i++){
    if(dp[m][k]<=dp[i][k-1]+w[i+1][m]){
        //if(m==s-1 && k==s) cout<<"!"<<i<<" "<<dp[m][k]<<" "<<dp[i][k-1]+w[i+1][m]<<endl;
        dp[m][k]=dp[i][k-1]+w[i+1][m];
        tmp=i;
    }
}
resi(k,l,m-1,x,tmp);
resi(k,m+1,d,tmp,y);
}

int main()
{
    std::ios_base::sync_with_stdio(0);
    cin>>r>>s;
    for(i=0;i<r;i++){
        for(j=0;j<s;j++){
            cin>>c;
            if(c=='.') a[i][j]=-1;
            else a[i][j]=c-'0';
        }
    }
    for(i=0;i<r*s;i++){
        l=d=i%s;
        sum=0;
        if(a[i/s][i%s]!=-1){
            dfs(i);
            t[l][d]+=sum;
        }
    }
    for(i=0;i<s;i++){
        len[i][s-1]=t[i][s-1];
        for(j=s-2;j>=i;j--){
            len[i][j]=len[i][j+1]+t[i][j];
        }
        w[i][i]=len[i][i];
    }
    for(i=1;i<s;i++){
        for(j=i;j<s;j++){
            sum=0;
            w[j-i][j]=w[j-i+1][j]+len[j-i][j];
        }
    }
    for(i=0;i<s;i++) dp[i][1]=w[0][i];
    for(i=2;i<=s;i++) resi(i,0,s-1,0,s-1);
    /*
    for(i=2;i<=s;i++){
        for(j=i-1;j<s;j++){
            dp[j][i]=0;
            for(int k=0;k<j;k++){
                dp[j][i]=max(dp[k][i-1]+w[k+1][j],dp[j][i]);
            }
        }
    }*/
    for(i=1;i<=s;i++){
        long long ans=0;
        for(j=i-1;j<s;j++) ans=max(ans,dp[j][i]);
        cout<<ans<<endl;
    }
    return 0;
}

Compilation message

nafta.cpp: In function 'void resi(int, int, int, int, int)':
nafta.cpp:31:5: warning: 'tmp' may be used uninitialized in this function [-Wmaybe-uninitialized]
 resi(k,l,m-1,x,tmp);
 ~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1408 KB Output is correct
2 Correct 3 ms 1408 KB Output is correct
3 Incorrect 3 ms 1280 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1408 KB Output is correct
2 Correct 3 ms 1408 KB Output is correct
3 Incorrect 3 ms 1280 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1408 KB Output is correct
2 Correct 3 ms 1408 KB Output is correct
3 Incorrect 3 ms 1280 KB Output isn't correct
4 Halted 0 ms 0 KB -