Submission #1224776

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224776		nh0902	Nafta (COI15_nafta)	C++20	100 / 100	280 ms	108200 KiB

nafta

#include <bits/stdc++.h>

using namespace std;

//#define int long long

const int N = 2e3 + 10;

const int M = 3e5 + 10;

const int inf = 1e9;

const int mod = 1e9 + 7;

int R, S, a[N][N];

int sum[N][N];
bool id[N][N];
int cur, cur_sum;
int dx[4] = {0, 0, 1, - 1};
int dy[4] = {1, - 1, 0, 0};

pair<int, int> dfs(int x, int y) {
    id[x][y] = cur;
    cur_sum += a[x][y];

    int l = y;
    int r = y;

    for (int t = 0; t < 4; t ++) {
        int i = x + dx[t];
        int j = y + dy[t];
        if (0 < i && i <= R && 0 < j && j <= S && a[i][j] != - 1 && id[i][j] == 0) {
            pair<int, int> p = dfs(i, j);
            l = min(l, p.first);
            r = max(r, p.second);
        }
    }

    return {l, r};
}

void prep() {
    cin >> R >> S;
    char c;
    for (int i = 1; i <= R; i ++) {
        for (int j = 1; j <= S; j ++) {
            cin >> c;
            if (c == '.') a[i][j] = - 1;
            else a[i][j] = c - '0';
        }
    }

    for (int i = 1; i <= R; i ++) {
        for (int j = 1; j <= S; j ++) {
            if (a[i][j] == - 1 || id[i][j] > 0) continue;
            cur ++;
            cur_sum = 0;
            auto [l, r] = dfs(i, j);
            for (int k = l; k <= r; k ++) sum[k][l] += cur_sum;
        }
    }

    for (int i = 1; i <= S; i ++) {
        for (int j = S; j >= 1; j --) {
            sum[i][j] += sum[i][j + 1];
        }
    }

}

int cost(int i, int j) {
    return sum[j][i + 1];
}

int dp[N][N];
int ans[N];

void dvc(int l, int r, int x, int y, int k) {

    if (l > r) return;

    int m = (l + r) / 2;
    dp[m][k] = dp[x][k - 1] + cost(x, m);
    int otp = x;

    for (int i = x + 1; i <= min(m - 1, y); i ++) {
        if (dp[i][k - 1] + cost(i, m) > dp[m][k]) {
            dp[m][k] = dp[i][k - 1] + cost(i, m);
            otp = i;
        }
    }

    ans[k] = max(ans[k], dp[m][k]);

    dvc(l, m - 1, x, otp, k);
    dvc(m + 1, r, otp, y, k);
}

void solve() {
    for (int i = 1; i <= S; i ++) {
        dvc(1, S, 0, S, i);
        ans[i] = max(ans[i], ans[i - 1]);
        cout << ans[i] << "\n";
    }

}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    prep();
    solve();

    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 66 / 66