oj.uz

Submission #108093

# Submission time Handle Problem Language Result Execution time Memory
108093 2019-04-27T09:56:25 Z igzi Nafta (COI15_nafta) C++17
34 / 100
 1000 ms 78080 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=0;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
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1408 KB Output is correct
2 Correct 4 ms 1408 KB Output is correct
3 Correct 4 ms 1328 KB Output is correct
4 Correct 4 ms 1408 KB Output is correct
5 Correct 3 ms 1408 KB Output is correct
6 Correct 3 ms 1280 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1408 KB Output is correct
2 Correct 4 ms 1408 KB Output is correct
3 Correct 4 ms 1328 KB Output is correct
4 Correct 4 ms 1408 KB Output is correct
5 Correct 3 ms 1408 KB Output is correct
6 Correct 3 ms 1280 KB Output is correct
7 Correct 51 ms 8156 KB Output is correct
8 Correct 39 ms 8184 KB Output is correct
9 Correct 42 ms 8388 KB Output is correct
10 Correct 41 ms 8184 KB Output is correct
11 Correct 36 ms 8060 KB Output is correct
12 Correct 36 ms 7416 KB Output is correct

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1408 KB Output is correct
2 Correct 4 ms 1408 KB Output is correct
3 Correct 4 ms 1328 KB Output is correct
4 Correct 4 ms 1408 KB Output is correct
5 Correct 3 ms 1408 KB Output is correct
6 Correct 3 ms 1280 KB Output is correct
7 Correct 51 ms 8156 KB Output is correct
8 Correct 39 ms 8184 KB Output is correct
9 Correct 42 ms 8388 KB Output is correct
10 Correct 41 ms 8184 KB Output is correct
11 Correct 36 ms 8060 KB Output is correct
12 Correct 36 ms 7416 KB Output is correct
13 Execution timed out 1078 ms 78080 KB Time limit exceeded
14 Halted 0 ms 0 KB -