oj.uz

Submission #411289

# Submission time Handle Problem Language Result Execution time Memory
411289 2021-05-25T00:40:26 Z ScarletS Nafta (COI15_nafta) C++17
34 / 100
 1000 ms 83376 KB 
#include <bits/stdc++.h>
#define ll long long
#define sz(x) (int)(x).size()
using namespace std;

const int N = 2002;
int n,m,dp[N][N],C[N],ol[N][N],ct[N],l,r,t;
char s[N][N];
bitset<N> done[N];
vector<array<int,2>> d = {{0,-1},{0,1},{-1,0},{1,0}};

bool ok(int x, int y)
{
    if (0<x&&0<y&&x<=n&&y<=m&&s[x][y]!='.'&&!done[x][y])
        return 1;
    return 0;
}

void dfs(int x, int y)
{
    done[x][y]=1;
    l=min(l,y);
    r=max(r,y);
    t+=(s[x][y]-'0');
    for (auto i : d)
        if (ok(x+i[0],y+i[1]))
            dfs(x+i[0],y+i[1]);
}

void solve(int i, int l, int r, int optL, int optR)
{
    if (l>r)
        return;
    int m=l+(r-l)/2,best=-1,k=-1;
    for (int j=optL;j<=m;++j)
        if (best<dp[i-1][j-1]+C[m]-ol[j-1][m])
        {
            best=dp[i-1][j-1]+C[m]-ol[j-1][m];
            k=j;
        }
    dp[i][m]=best;
    solve(i,l,m-1,optL,k);
    solve(i,m+1,r,k,optR);
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    for (int i=1;i<=n;++i)
        for (int j=1;j<=m;++j)
            cin>>s[i][j];
    for (int i=1;i<=n;++i)
        for (int j=1;j<=m;++j)
            if (ok(i,j))
            {
                t=0;
                l=j;
                r=j;
                dfs(i,j);
                ct[l]+=t;
                ct[r+1]-=t;
                for (int k=l;k<=r;++k)
                    ol[l][k]+=t;
            }
    for (int i=1;i<=m;++i)
    {
        ct[i]+=ct[i-1];
        C[i]+=ct[i];
    }
    for (int j=1;j<=m;++j)
        for (int i=1;i<=j;++i)
            ol[i][j]+=ol[i-1][j];
    // for (int i=1;i<=m;++i)
    //     for (int j=i;j<=m;++j)
    //         cout<<i<<" "<<j<<": "<<C[j]-ol[i-1][j]<<"\n";
    // return 0;
    for (int i=1;i<=m;++i)
    {
        solve(i,1,m,1,m);
        for (int j=2;j<=m;++j)
            dp[i][j]=max(dp[i][j-1],dp[i][j]);
        cout<<dp[i][m]<<"\n";
    }
    return 0;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 844 KB Output is correct
2 Correct 1 ms 832 KB Output is correct
3 Correct 1 ms 844 KB Output is correct
4 Correct 1 ms 844 KB Output is correct
5 Correct 1 ms 844 KB Output is correct
6 Correct 1 ms 844 KB Output is correct
7 Correct 8 ms 4044 KB Output is correct
8 Correct 9 ms 3992 KB Output is correct
9 Correct 10 ms 4956 KB Output is correct
10 Correct 7 ms 4044 KB Output is correct
11 Correct 9 ms 4044 KB Output is correct
12 Correct 13 ms 3988 KB Output is correct

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 844 KB Output is correct
2 Correct 1 ms 832 KB Output is correct
3 Correct 1 ms 844 KB Output is correct
4 Correct 1 ms 844 KB Output is correct
5 Correct 1 ms 844 KB Output is correct
6 Correct 1 ms 844 KB Output is correct
7 Correct 8 ms 4044 KB Output is correct
8 Correct 9 ms 3992 KB Output is correct
9 Correct 10 ms 4956 KB Output is correct
10 Correct 7 ms 4044 KB Output is correct
11 Correct 9 ms 4044 KB Output is correct
12 Correct 13 ms 3988 KB Output is correct
13 Correct 336 ms 38304 KB Output is correct
14 Correct 387 ms 38092 KB Output is correct
15 Correct 468 ms 83376 KB Output is correct
16 Correct 325 ms 38160 KB Output is correct
17 Correct 839 ms 38140 KB Output is correct
18 Execution timed out 1055 ms 36520 KB Time limit exceeded