제출 #1137861

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1137861		gyg	Nafta (COI15_nafta)	C++20	100 / 100	728 ms	353452 KiB

nafta

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define arr array 
#define vec vector 
#define pii pair<int, int>
#define fir first 
#define sec second
const int R = 2e3 + 5, C = 2e3 + 5, INF = 1e18;

int r, c;
arr<arr<int, C>, R> a;

int nm_cls;
arr<arr<int, C>, R> cl;
arr<int, R * C> vl;
arr<pii, R * C> rng;
void dfs(int i, int j) {
    cl[i][j] = nm_cls, vl[nm_cls] += a[i][j];
    rng[nm_cls].fir = min(rng[nm_cls].fir, j), rng[nm_cls].sec = max(rng[nm_cls].sec, j); 
    vec<pii> adj = {{i - 1, j}, {i + 1, j}, {i, j - 1}, {i, j + 1}};
    for (pii x : adj) {
        if (x.fir < 1 || x.fir > r || x.sec < 1 || x.sec > c) continue;
        if (a[x.fir][x.sec] == -1) continue;
        if (cl[x.fir][x.sec]) continue;
        dfs(x.fir, x.sec);
    }
}
arr<arr<int, C>, C> cst;
int cst_qry(int l, int r) {
    if (l > r) return 0;
    return cst[r][r] - cst[l - 1][r] - cst[r][l - 1] + cst[l - 1][l - 1];
}
void cst_cmp() {
    for (int i = 1; i <= r; i++) 
        for (int j = 1; j <= c; j++) 
            if (a[i][j] != -1 && !cl[i][j]) 
                rng[++nm_cls] = {j, j}, dfs(i, j), cst[rng[nm_cls].fir][rng[nm_cls].sec] += vl[nm_cls];
    for (int i = 1; i <= c; i++)
        for (int j = 1; j <= c; j++)
            cst[i][j] = cst[i - 1][j] + cst[i][j - 1] - cst[i - 1][j - 1] + cst[i][j];

    // for (int i = 1; i <= nm_cls; i++) cout << rng[i].fir << " " << rng[i].sec << '\n';
}

arr<arr<int, C>, C> dp;
void dnc(int k, int l = 1, int r = c, int lw = 1, int hg = c) {
    if (lw > hg) return;
    int md = (lw + hg) / 2;
    pii bst = {INF, -1};
    for (int i = max(l, 1ll); i <= min(r, md); i++)
        bst = min(bst, {dp[i - 1][k - 1] + cst_qry(i, md - 1), i});
    dp[md][k] = bst.fir;
    dnc(k, l, bst.sec, lw, md - 1), dnc(k, bst.sec, r, md + 1, hg);
}

void dp_cmp() {
    for (int i = 1; i <= c; i++) dp[i][1] = cst_qry(1, i - 1);
    for (int k = 2; k <= c; k++) {
        // for (int i = 1; i <= c; i++) {
        //     dp[i][k] = INF;
        //     for (int j = 1; j <= i; j++)
        //         dp[i][k] = min(dp[i][k], dp[j - 1][k - 1] + cst_qry(j, i - 1));
        //     // cout << k << " " << i << ": " << dp[i][k] << '\n';
        // }
        dnc(k);
    }
}

signed main() {
    // freopen("in", "r", stdin);
    cin.sync_with_stdio(false), cin.tie(0);
    cin >> r >> c;
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) {
            char x; cin >> x;
            a[i][j] = (x == '.') ? -1 : x - '0';
        }
    }
    cst_cmp();
    dp_cmp();

    int whl = 0;
    for (int i = 1; i <= r; i++)
        for (int j = 1; j <= c; j++)    
            if (a[i][j] != -1) whl += a[i][j];
    for (int k = 1; k <= c; k++) {
        int ans = INF;
        for (int i = 1; i <= c; i++) ans = min(ans, dp[i][k] + cst_qry(i + 1, c));
        ans = whl - ans;
        cout << ans << '\n';
    }
}

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