Submission #1078230

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078230		BF001	Nafta (COI15_nafta)	C++17	100 / 100	407 ms	152144 KiB

nafta

#include<bits/stdc++.h>
using namespace std;
 
#define N 2005
#define int long long
#define oo 1e18

int cst[N][N], par[N * N], mi[N * N], n, m, sum[N * N], vs[N * N];
char a[N][N];
int dx[4] = {0, 1, -1, 0};
int dy[4] = {1, 0, 0, -1};
vector<int> cur, lst;

int find(int u){
    if (u == par[u]) return u;
    return par[u] = find(par[u]);
}

void unin(int u, int v){
    u = find(u);
    v = find(v);
    if (u == v) return;
    par[v] = u;
    sum[u] += sum[v];
    mi[u] = min(mi[u], mi[v]);
}

bool in(int x, int y){
    return (a[x][y] >= '0' && a[x][y] <= '9' && x >= 1 && x <= n && y >= 1 && y <= m);
}
 
int getidx(int x, int y){
    return (x - 1) * m + y;
}

void cpt(int l, int r, int ol, int opr){
    if (l > r) return;
    int mid = (l + r) >> 1;
    int bst = -oo, pos = -1;
    for (int t = ol; t <= min(opr, mid); t++){
        if (bst < lst[t - 1] + cst[t][mid]){
            bst = lst[t - 1] + cst[t][mid];
            pos = t;
        }
    }
    cur[mid] = bst;
    cpt(l, mid - 1, ol, pos);
    cpt(mid + 1, r, pos, opr);
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            cin >> a[i][j];
            if (a[i][j] >= '0' && a[i][j] <= '9'){
                par[getidx(i, j)] = getidx(i, j);
                mi[getidx(i, j)] = j;
                sum[getidx(i, j)] = a[i][j] - '0';
            }
        }
    }

    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            if (!in(i, j)) continue;
            for (int k = 0; k < 4; k++){
                int newi = i + dx[k];
                int newj = j + dy[k];
                if (!in(newi, newj)) continue;
                unin(getidx(i, j), getidx(newi, newj));
            }
        }
    }
 
    for (int j = 1; j <= m; j++){
        for (int i = 1; i <= n; i++){
            if (!in(i, j)) continue;
            int u = find(getidx(i, j));
            if (vs[u]) continue;
            vs[u] = 1;
            cst[mi[u]][j] += sum[u];
        }
        for (int i = 1; i <= n; i++){
            if (!in(i, j)) continue;
            int u = find(getidx(i, j));
            vs[u] = 0;
        }
        for (int i = j - 1; i >= 1; i--){
            cst[i][j] += cst[i + 1][j];
        }
    }

    cur.resize(m + 1, 0);
    lst.resize(m + 1, 0);

    for (int k = 1; k <= m; k++){
        lst = cur;
        cpt(1, m, 1, m);
        int res = 0;
        for (int i = 1; i <= m; i++) res = max(res, cur[i]);
        cout << res << "\n";
    } 

    return 0;
}

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