Submission #893293

#	Time	Username	Problem	Language	Result	Execution time	Memory
893293		coloboxx	Nafta (COI15_nafta)	C++17	0 / 100	2 ms	18780 KiB

nafta

// #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], opt[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, -1);
    for (int k = optl; k <= min(mid - 1, 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++);

    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) {
        C[i][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: 0 / 11
• Subtask 2: 0 / 23
• Subtask 3: 0 / 66