oj.uz

Submission #108102

# Submission time Handle Problem Language Result Execution time Memory
108102 2019-04-27T10:21:39 Z igzi Nafta (COI15_nafta) C++17
100 / 100
 934 ms 114764 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 4 ms 1408 KB Output is correct
2 Correct 4 ms 1408 KB Output is correct
3 Correct 3 ms 1324 KB Output is correct
4 Correct 3 ms 1408 KB Output is correct
5 Correct 3 ms 1380 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 4 ms 1408 KB Output is correct
2 Correct 4 ms 1408 KB Output is correct
3 Correct 3 ms 1324 KB Output is correct
4 Correct 3 ms 1408 KB Output is correct
5 Correct 3 ms 1380 KB Output is correct
6 Correct 3 ms 1280 KB Output is correct
7 Correct 16 ms 8220 KB Output is correct
8 Correct 16 ms 8320 KB Output is correct
9 Correct 17 ms 8508 KB Output is correct
10 Correct 19 ms 8312 KB Output is correct
11 Correct 13 ms 8064 KB Output is correct
12 Correct 15 ms 7552 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1408 KB Output is correct
2 Correct 4 ms 1408 KB Output is correct
3 Correct 3 ms 1324 KB Output is correct
4 Correct 3 ms 1408 KB Output is correct
5 Correct 3 ms 1380 KB Output is correct
6 Correct 3 ms 1280 KB Output is correct
7 Correct 16 ms 8220 KB Output is correct
8 Correct 16 ms 8320 KB Output is correct
9 Correct 17 ms 8508 KB Output is correct
10 Correct 19 ms 8312 KB Output is correct
11 Correct 13 ms 8064 KB Output is correct
12 Correct 15 ms 7552 KB Output is correct
13 Correct 638 ms 101104 KB Output is correct
14 Correct 776 ms 101640 KB Output is correct
15 Correct 934 ms 114764 KB Output is correct
16 Correct 714 ms 101380 KB Output is correct
17 Correct 684 ms 98504 KB Output is correct
18 Correct 553 ms 96948 KB Output is correct