oj.uz

Submission #647191

# Submission time Handle Problem Language Result Execution time Memory
647191 2022-10-01T21:53:05 Z danikoynov Nafta (COI15_nafta) C++14
34 / 100
 1000 ms 50100 KB 
/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

struct cell
{
    int x, y;

    cell(int _x = 0, int _y = 0)
    {
        x = _x;
        y = _y;
    }

    cell operator + (const cell & c) const
    {
        cell r;
        r.x = x + c.x;
        r.y = y + c.y;
        return r;
    }
};

cell neib[4] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};

const int maxn = 2010;
int n, m, sum[maxn * maxn], used[maxn][maxn];
int lm[maxn * maxn], rm[maxn * maxn], met[maxn * maxn];
char c[maxn][maxn];
void bfs(int i, int j)
{
    cell st(i, j);
    queue < cell > q;
    q.push(st);
    while(!q.empty())
    {
        st = q.front();
        q.pop();
        for (int i = 0; i < 4; i ++)
        {
            cell nb = st + neib[i];
            if (!used[nb.x][nb.y])
            {
                used[nb.x][nb.y] = used[st.x][st.y];
                q.push(nb);
            }
        }
    }
}

int cost[maxn][maxn], df[maxn], dp[maxn][maxn];
void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
        {
            cin >> c[i][j];
            if (c[i][j] == '.')
                used[i][j] = 1;
        }

    for (int i = 0; i <= n + 1; i ++)
        used[i][0] = used[i][m + 1] = 1;

    for (int j = 0; j <= m + 1; j ++)
        used[0][j] = used[n + 1][j] = 1;

    int cnt = 0;
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
        {
            if (!used[i][j])
            {
                cnt ++;
                used[i][j] = cnt;
                bfs(i, j);
            }
        }

    for (int i = 1; i <= cnt; i ++)
        lm[i] = m + 1, rm[i] = 0;

    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
        {
            if (c[i][j] == '.')
            {
                used[i][j] = 0;
                continue;
            }
            sum[used[i][j]] += (int)(c[i][j] - '0');
            lm[used[i][j]] = min(lm[used[i][j]], j);
            rm[used[i][j]] = max(rm[used[i][j]], j);
        }



    for (int j = 1; j <= m; j ++)
    {
        int cur = 0;
        for (int i = 1; i <= n; i ++)
        {
            if (!met[used[i][j]])
            {
                met[used[i][j]] = 1;
                df[rm[used[i][j]]] += sum[used[i][j]];

                cur += sum[used[i][j]];
            }

        }

        for (int i = 1; i <= n; i ++)
            met[used[i][j]] = 0;
        for (int j1 = 0; j1 < j; j1 ++)
            cost[j1][j] += cur;

        int to_rem = cur - df[j];
        for (int j1 = j + 1; j1 <= m; j1 ++)
        {
            cost[j][j1] -= to_rem;
            to_rem -= df[j1];

        }

        for (int j1 = 1; j1 <= m; j1 ++)
            df[j1] = 0;
    }



    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
        for (int i1 = 0; i1 < i; i1 ++)
    {
        dp[i][j] = max(dp[i][j], dp[i1][j - 1] + cost[i1][i]);
        dp[i][j] = max(dp[i][j], dp[i - 1][j]);
    }

    for (int j = 1; j <= m; j ++)
        cout << dp[n][j] << endl;




}

int main()
{
    solve();
    return 0;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 1080 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 2 ms 980 KB Output is correct
5 Correct 2 ms 980 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 40 ms 5696 KB Output is correct
8 Correct 40 ms 5580 KB Output is correct
9 Correct 39 ms 5488 KB Output is correct
10 Correct 39 ms 5616 KB Output is correct
11 Correct 38 ms 5480 KB Output is correct
12 Correct 40 ms 5424 KB Output is correct

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 1080 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 2 ms 980 KB Output is correct
5 Correct 2 ms 980 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 40 ms 5696 KB Output is correct
8 Correct 40 ms 5580 KB Output is correct
9 Correct 39 ms 5488 KB Output is correct
10 Correct 39 ms 5616 KB Output is correct
11 Correct 38 ms 5480 KB Output is correct
12 Correct 40 ms 5424 KB Output is correct
13 Execution timed out 1097 ms 50100 KB Time limit exceeded
14 Halted 0 ms 0 KB -