oj.uz

Submission #893301

# Submission time Handle Problem Language Result Execution time Memory
893301 2023-12-26T21:42:44 Z coloboxx Nafta (COI15_nafta) C++17
100 / 100
 398 ms 138324 KB 
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("avx,avx2,sse2,sse3,ssse3,sse4,lzcnt,popcnt")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define ll long long
#define ull unsigned ll
#define point pair<int, int>
#define X first
#define Y second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define show(x) cerr << (#x) << " = " << x << '\n'
#define print(l, r) cerr << "[" << (#l) << ", " << (#r) << "] = ", _print(l, r), cerr << '\n'
#define fast_io ios_base::sync_with_stdio(0), cin.tie(0)
template<class iter>
void _print(iter _first, iter _last) {
    while (_first != _last) {
        std::cerr << *(_first) << ' ';
        ++_first;
    }
}

const int N = 1 << 11;
const int S = 2e7 + 64;
const int INF = 1e9 + 9;
const ll MAX = 2e18 + 18;
const int LOG = 30;
const int MOD = 998244353;
const int P = 79;
const int B = 256;

using namespace std;
using namespace __gnu_pbds;

const int dx[4] = {-1, +1, 0, 0};
const int dy[4] = {0, 0, -1, +1};

char a[N][N];
bool used[N][N];

int n, m, lb[N * N], rb[N * N], cost[N * N], prep[N][N], C[N][N], dp[N][N];

void dfs(int x, int y, int comp) {
    used[x][y] = true;
    cost[comp] += a[x][y] - '0';
    lb[comp] = min(lb[comp], y);
    rb[comp] = max(rb[comp], y);

    for (int i = 0; i < 4; ++i) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx >= n || ny >= m || nx < 0 || ny < 0)
            continue;

        if (a[nx][ny] != '.' && !used[nx][ny])
            dfs(nx, ny, comp);
    }
}

void solve(int l, int r, int optl, int optr, int j) {
    if (l > r)
        return;

    int mid = (l + r) >> 1;
    point nxt(-INF, -INF);
    for (int k = optl; k <= min(mid, optr); ++k)
        nxt = max(nxt, point(dp[k][j - 1] + C[k][mid], -k));

    dp[mid][j] = nxt.first;
    solve(l, mid - 1, optl, -nxt.second, j);
    solve(mid + 1, r, -nxt.second, optr, j);
}

int32_t main() {
    fast_io;

    cin >> n >> m;

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> a[i][j];

    int cnt = 0;

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if (!used[i][j] && a[i][j] != '.')
                lb[cnt] = rb[cnt] = j, dfs(i, j, cnt), ++cnt;

    for (int i = 0; i < cnt; ++i)
        prep[lb[i]][rb[i]] += cost[i];

    for (int len = 2; len <= m; ++len)
        for (int i = 0, j = i + len - 1; j < m; ++i, ++j)
            prep[i][j] += prep[i + 1][j] + prep[i][j - 1] - prep[i + 1][j - 1];

    for (int i = 0; i < m; ++i) {
        dp[i][1] = prep[0][m - 1] - (i ? prep[0][i - 1] : 0) - prep[i + 1][m - 1];
        for (int j = i + 1; j < m; ++j)
            C[i][j] = prep[i + 1][m - 1] - prep[j + 1][m - 1] - prep[i + 1][j - 1];
    }

    for (int j = 2; j <= m; ++j)
        solve(0, m - 1, 0, m - 1, j);

    for (int j = 1; j <= m; ++j) {
        int mx = 0;
        for (int i = 0; i < m; ++i)
            mx = max(mx, dp[i][j]);
        cout << mx << '\n';
    }
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 18780 KB Output is correct
2 Correct 2 ms 18780 KB Output is correct
3 Correct 4 ms 19036 KB Output is correct
4 Correct 2 ms 18776 KB Output is correct
5 Correct 3 ms 18780 KB Output is correct
6 Correct 2 ms 18780 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 18780 KB Output is correct
2 Correct 2 ms 18780 KB Output is correct
3 Correct 4 ms 19036 KB Output is correct
4 Correct 2 ms 18776 KB Output is correct
5 Correct 3 ms 18780 KB Output is correct
6 Correct 2 ms 18780 KB Output is correct
7 Correct 9 ms 27592 KB Output is correct
8 Correct 9 ms 27480 KB Output is correct
9 Correct 11 ms 29276 KB Output is correct
10 Correct 8 ms 27480 KB Output is correct
11 Correct 8 ms 27484 KB Output is correct
12 Correct 9 ms 25692 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 18780 KB Output is correct
2 Correct 2 ms 18780 KB Output is correct
3 Correct 4 ms 19036 KB Output is correct
4 Correct 2 ms 18776 KB Output is correct
5 Correct 3 ms 18780 KB Output is correct
6 Correct 2 ms 18780 KB Output is correct
7 Correct 9 ms 27592 KB Output is correct
8 Correct 9 ms 27480 KB Output is correct
9 Correct 11 ms 29276 KB Output is correct
10 Correct 8 ms 27480 KB Output is correct
11 Correct 8 ms 27484 KB Output is correct
12 Correct 9 ms 25692 KB Output is correct
13 Correct 288 ms 68656 KB Output is correct
14 Correct 319 ms 67788 KB Output is correct
15 Correct 398 ms 138324 KB Output is correct
16 Correct 285 ms 67640 KB Output is correct
17 Correct 325 ms 62652 KB Output is correct
18 Correct 324 ms 62696 KB Output is correct