oj.uz

Submission #732218

# Submission time Handle Problem Language Result Execution time Memory
732218 2023-04-28T16:59:20 Z finn__ Nafta (COI15_nafta) C++17
100 / 100
 477 ms 84156 KB 
#include <bits/stdc++.h>
using namespace std;

constexpr size_t N = 2001;
constexpr int di[4] = {1, 0, -1, 0}, dj[4] = {0, 1, 0, -1};

string grid[N];
unsigned comp[N][N], rlm[N * N];
int64_t val[N * N], w[N][N], f[N][N], g[N];

void dcdp(size_t a, size_t b, size_t u, size_t v, size_t j)
{
    size_t mid = (a + b) / 2, opt_i = u;
    for (size_t i = u; i <= v && i < mid; ++i)
        if (f[j - 1][i] + w[mid - 1][mid - 1] - (i ? w[i - 1][mid - 1] : 0) > f[j][mid])
            f[j][mid] = f[j - 1][i] + w[mid - 1][mid - 1] - (i ? w[i - 1][mid - 1] : 0),
            opt_i = i;
    if (a != b)
    {
        dcdp(a, (a + b) / 2, u, opt_i, j);
        dcdp((a + b) / 2 + 1, b, opt_i, v, j);
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    size_t n, m;
    cin >> n >> m;
    for (size_t i = 0; i < n; ++i)
        cin >> grid[i];

    memset(comp, 255, sizeof comp);
    size_t c = 0;
    for (size_t i = 0; i < n; ++i)
        for (size_t j = 0; j < m; ++j)
            if (comp[i][j] == UINT_MAX && grid[i][j] != '.')
            {
                queue<pair<unsigned, unsigned>> q({{i, j}});
                comp[i][j] = c;
                val[c] = grid[i][j] - '0';
                rlm[c] = j;
                while (!q.empty())
                {
                    auto const [u, v] = q.front();
                    q.pop();
                    for (size_t k = 0; k < 4; ++k)
                        if (u + di[k] < n && v + dj[k] < m && grid[u + di[k]][v + dj[k]] != '.' &&
                            comp[u + di[k]][v + dj[k]] == UINT_MAX)
                        {
                            comp[u + di[k]][v + dj[k]] = c;
                            val[c] += grid[u + di[k]][v + dj[k]] - '0';
                            rlm[c] = max(rlm[c], v + dj[k]);
                            q.emplace(u + di[k], v + dj[k]);
                        }
                }
                ++c;
            }

    for (size_t j = 0; j < m; ++j)
    {
        vector<unsigned> components;
        for (size_t i = 0; i < n; ++i)
            if (comp[i][j] != UINT_MAX)
                components.push_back(comp[i][j]);
        sort(components.begin(), components.end());
        components.resize(unique(components.begin(), components.end()) - components.begin());
        int64_t x = 0;
        for (unsigned const &u : components)
            x += val[u];
        w[j][j] = x;
        sort(components.begin(), components.end(), [](auto const &a, auto const &b)
             { return rlm[a] < rlm[b]; });
        auto it = components.begin();
        for (size_t k = j + 1; k < m; ++k)
        {
            while (it != components.end() && rlm[*it] < k)
                x -= val[*it], ++it;
            w[j][k] = x;
        }
    }

    for (size_t j = 1; j <= m; ++j)
        dcdp(1, m, 0, m - 1, j), cout << *max_element(f[j] + 1, f[j] + 1 + m) << '\n';
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16468 KB Output is correct
2 Correct 8 ms 16468 KB Output is correct
3 Correct 7 ms 16408 KB Output is correct
4 Correct 7 ms 16508 KB Output is correct
5 Correct 8 ms 16468 KB Output is correct
6 Correct 8 ms 16468 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16468 KB Output is correct
2 Correct 8 ms 16468 KB Output is correct
3 Correct 7 ms 16408 KB Output is correct
4 Correct 7 ms 16508 KB Output is correct
5 Correct 8 ms 16468 KB Output is correct
6 Correct 8 ms 16468 KB Output is correct
7 Correct 16 ms 19912 KB Output is correct
8 Correct 17 ms 19724 KB Output is correct
9 Correct 17 ms 19708 KB Output is correct
10 Correct 16 ms 19804 KB Output is correct
11 Correct 20 ms 19688 KB Output is correct
12 Correct 14 ms 19668 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16468 KB Output is correct
2 Correct 8 ms 16468 KB Output is correct
3 Correct 7 ms 16408 KB Output is correct
4 Correct 7 ms 16508 KB Output is correct
5 Correct 8 ms 16468 KB Output is correct
6 Correct 8 ms 16468 KB Output is correct
7 Correct 16 ms 19912 KB Output is correct
8 Correct 17 ms 19724 KB Output is correct
9 Correct 17 ms 19708 KB Output is correct
10 Correct 16 ms 19804 KB Output is correct
11 Correct 20 ms 19688 KB Output is correct
12 Correct 14 ms 19668 KB Output is correct
13 Correct 384 ms 84156 KB Output is correct
14 Correct 463 ms 81320 KB Output is correct
15 Correct 477 ms 78520 KB Output is correct
16 Correct 387 ms 81096 KB Output is correct
17 Correct 447 ms 78428 KB Output is correct
18 Correct 431 ms 78248 KB Output is correct