oj.uz

Submission #1078227

# Submission time Handle Problem Language Result Execution time Memory
1078227 2024-08-27T14:16:25 Z BF001 Nafta (COI15_nafta) C++17
100 / 100
 375 ms 156332 KB 
#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], dp[N][N], res[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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 0 ms 860 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 0 ms 860 KB Output is correct
7 Correct 10 ms 5420 KB Output is correct
8 Correct 8 ms 5468 KB Output is correct
9 Correct 7 ms 5416 KB Output is correct
10 Correct 5 ms 5464 KB Output is correct
11 Correct 7 ms 5464 KB Output is correct
12 Correct 6 ms 5468 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 0 ms 860 KB Output is correct
7 Correct 10 ms 5420 KB Output is correct
8 Correct 8 ms 5468 KB Output is correct
9 Correct 7 ms 5416 KB Output is correct
10 Correct 5 ms 5464 KB Output is correct
11 Correct 7 ms 5464 KB Output is correct
12 Correct 6 ms 5468 KB Output is correct
13 Correct 313 ms 156220 KB Output is correct
14 Correct 375 ms 156332 KB Output is correct
15 Correct 335 ms 155476 KB Output is correct
16 Correct 257 ms 109636 KB Output is correct
17 Correct 239 ms 109292 KB Output is correct
18 Correct 238 ms 109016 KB Output is correct