oj.uz

Submission #108083

# Submission time Handle Problem Language Result Execution time Memory
108083 2019-04-27T09:00:57 Z igzi Nafta (COI15_nafta) C++17
34 / 100
 1000 ms 45760 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],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);
}

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++){
        sum=0;
        for(j=i;j<s;j++) sum+=t[i][j];
        w[i][i]=sum;
    }
    for(i=1;i<s;i++){
        for(j=i;j<s;j++){
            sum=0;
            for(int k=j;k<s;k++) sum+=t[j-i][k];
            w[j-i][j]=w[j-i+1][j]+sum;
        }
    }
    for(i=0;i<s;i++) dp[i][1]=w[0][i];
    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;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1152 KB Output is correct
2 Correct 3 ms 1152 KB Output is correct
3 Correct 3 ms 1024 KB Output is correct
4 Correct 4 ms 1152 KB Output is correct
5 Correct 3 ms 1152 KB Output is correct
6 Correct 3 ms 1024 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1152 KB Output is correct
2 Correct 3 ms 1152 KB Output is correct
3 Correct 3 ms 1024 KB Output is correct
4 Correct 4 ms 1152 KB Output is correct
5 Correct 3 ms 1152 KB Output is correct
6 Correct 3 ms 1024 KB Output is correct
7 Correct 31 ms 6368 KB Output is correct
8 Correct 34 ms 6368 KB Output is correct
9 Correct 40 ms 6568 KB Output is correct
10 Correct 34 ms 6272 KB Output is correct
11 Correct 43 ms 6264 KB Output is correct
12 Correct 39 ms 5632 KB Output is correct

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1152 KB Output is correct
2 Correct 3 ms 1152 KB Output is correct
3 Correct 3 ms 1024 KB Output is correct
4 Correct 4 ms 1152 KB Output is correct
5 Correct 3 ms 1152 KB Output is correct
6 Correct 3 ms 1024 KB Output is correct
7 Correct 31 ms 6368 KB Output is correct
8 Correct 34 ms 6368 KB Output is correct
9 Correct 40 ms 6568 KB Output is correct
10 Correct 34 ms 6272 KB Output is correct
11 Correct 43 ms 6264 KB Output is correct
12 Correct 39 ms 5632 KB Output is correct
13 Execution timed out 1057 ms 45760 KB Time limit exceeded
14 Halted 0 ms 0 KB -