oj.uz

Submission #108084

# Submission time Handle Problem Language Result Execution time Memory
108084 2019-04-27T09:07:06 Z igzi Nafta (COI15_nafta) C++17
34 / 100
 1000 ms 78132 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);
}

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++){
        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 1408 KB Output is correct
2 Correct 3 ms 1408 KB Output is correct
3 Correct 3 ms 1152 KB Output is correct
4 Correct 3 ms 1408 KB Output is correct
5 Correct 3 ms 1408 KB Output is correct
6 Correct 4 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 1152 KB Output is correct
4 Correct 3 ms 1408 KB Output is correct
5 Correct 3 ms 1408 KB Output is correct
6 Correct 4 ms 1280 KB Output is correct
7 Correct 36 ms 7824 KB Output is correct
8 Correct 30 ms 7808 KB Output is correct
9 Correct 40 ms 7936 KB Output is correct
10 Correct 31 ms 7800 KB Output is correct
11 Correct 31 ms 7800 KB Output is correct
12 Correct 28 ms 7160 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 3 ms 1408 KB Output is correct
3 Correct 3 ms 1152 KB Output is correct
4 Correct 3 ms 1408 KB Output is correct
5 Correct 3 ms 1408 KB Output is correct
6 Correct 4 ms 1280 KB Output is correct
7 Correct 36 ms 7824 KB Output is correct
8 Correct 30 ms 7808 KB Output is correct
9 Correct 40 ms 7936 KB Output is correct
10 Correct 31 ms 7800 KB Output is correct
11 Correct 31 ms 7800 KB Output is correct
12 Correct 28 ms 7160 KB Output is correct
13 Execution timed out 1077 ms 78132 KB Time limit exceeded
14 Halted 0 ms 0 KB -