oj.uz

Submission #108098

# Submission time Handle Problem Language Result Execution time Memory
108098 2019-04-27T10:18:55 Z igzi Nafta (COI15_nafta) C++17
100 / 100
 818 ms 118320 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=max(0,x);i<min(m,y+1);i++){
    if(dp[m][k]<=dp[i][k-1]+w[i+1][m]){
        //if(m==s-4 && k==s-3) 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-1,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]);
            }
        }
    }*/
    //cout<<dp[44][45]<<" "<<w[45][45]<<endl;
    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 3 ms 1408 KB Output is correct
3 Correct 3 ms 1280 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 3 ms 1408 KB Output is correct
3 Correct 3 ms 1280 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 19 ms 8192 KB Output is correct
8 Correct 17 ms 8192 KB Output is correct
9 Correct 16 ms 8320 KB Output is correct
10 Correct 15 ms 8192 KB Output is correct
11 Correct 18 ms 8192 KB Output is correct
12 Correct 18 ms 7424 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1408 KB Output is correct
2 Correct 3 ms 1408 KB Output is correct
3 Correct 3 ms 1280 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 19 ms 8192 KB Output is correct
8 Correct 17 ms 8192 KB Output is correct
9 Correct 16 ms 8320 KB Output is correct
10 Correct 15 ms 8192 KB Output is correct
11 Correct 18 ms 8192 KB Output is correct
12 Correct 18 ms 7424 KB Output is correct
13 Correct 665 ms 101108 KB Output is correct
14 Correct 755 ms 105208 KB Output is correct
15 Correct 818 ms 118320 KB Output is correct
16 Correct 653 ms 104952 KB Output is correct
17 Correct 667 ms 102180 KB Output is correct
18 Correct 606 ms 100600 KB Output is correct