Submission #108098

#	Time	Username	Problem	Language	Result	Execution time	Memory
108098		igzi	Nafta (COI15_nafta)	C++17	100 / 100	818 ms	118320 KiB

nafta

#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 (stderr)

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 / 11
• Subtask 2: 23 / 23
• Subtask 3: 66 / 66