oj.uz

Submission #891806

# Submission time Handle Problem Language Result Execution time Memory
891806 2023-12-24T05:08:26 Z chanhchuong123 Nafta (COI15_nafta) C++14
100 / 100
 293 ms 108384 KB 
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r) {
	return uniform_int_distribution<int>(l, r)(rng);
}

#define ID(x, y) ((x - 1) * nCol + (y - 1))
const int dx[] = {-1, 0, 0, +1};
const int dy[] = {0, -1, +1, 0};
const int INF = 1e9 + 7;
const int MAX = 2020;
int nRow;
int nCol;
int f[MAX];
int g[MAX];
char a[MAX][MAX];
int pf[MAX][MAX];
int co[MAX][MAX];
int mn[MAX * MAX];
int mx[MAX * MAX];
int sum[MAX * MAX];
int lab[MAX * MAX];
bool used[MAX * MAX];

int findSet(int v) {
    return lab[v] < 0 ? v : lab[v] = findSet(lab[v]);
}

bool unionSet(int u, int v) {
    u = findSet(u);
    v = findSet(v);
    if (u == v) return false;
    if (lab[u] > lab[v]) swap(u, v);
    lab[u] += lab[v]; lab[v] = u;
    mx[u] = max(mx[u], mx[v]);
    mn[u] = min(mn[u], mn[v]);
    sum[u] += sum[v];
    return true;
}

void init(void) {
    cin >> nRow >> nCol;
    for (int i = 1; i <= nRow; ++i) {
        for (int j = 1; j <= nCol; ++j)
            cin >> a[i][j];
    }
    for (int i = 1; i <= nRow; ++i) for (int j = 1; j <= nCol; ++j) if (a[i][j] != '.') {
        mn[ID(i, j)] = j;
        mx[ID(i, j)] = j;
        lab[ID(i, j)] = -1;
        sum[ID(i, j)] = a[i][j] - '0';
    }
    for (int i = 1; i <= nRow; ++i) for (int j = 1; j <= nCol; ++j) if (a[i][j] != '.') {
        for (int k = 0; k < 4; ++k) {
            int x = i + dx[k], y = j + dy[k];
            if (x <= 0 || x > nRow) continue;
            if (y <= 0 || y > nCol) continue;
            if (a[x][y] != '.') unionSet(ID(i, j), ID(x, y));
        }
    }
    for (int j = 1; j <= nCol; ++j) {
        for (int i = 1; i <= nRow; ++i) if (a[i][j] != '.') {
            int root = findSet(ID(i, j));
            if (used[root] == false) {
                used[root] = true;
                pf[j][mn[root] + 0] += sum[root];
                pf[j][mx[root] + 1] -= sum[root];
            }
        }
        for (int k = 1; k <= nCol; ++k) {
            pf[j][k] += pf[j][k - 1];
        }
        for (int i = 1; i <= nRow; ++i) if (a[i][j] != '.') {
            int root = findSet(ID(i, j));
            used[root] = false;
        }
    }
    for (int i = 1; i <= nCol; ++i) {
        for (int j = i; j <= nCol; ++j)
            co[i][j] = pf[j][j] - pf[j][i];
    }
}

void calc(int l, int r, int optL, int optR) {
    if (l > r) return;
    int mid = l + r >> 1;
    pair<int, int> best(-INF, -1);
    for (int k = optL; k <= min(optR, mid - 1); ++k) best = max(best, make_pair(g[k] + co[k][mid], -k));
    f[mid] = best.fi; int opt = -best.se;
    calc(l, mid - 1, optL, opt);
    calc(mid + 1, r, opt, optR);
}

void process(void) {
    for (int i = 1; i <= nCol; ++i) {
        g[i] = pf[i][i];
        f[i] = g[i];
    }
    cout << *max_element(f + 1, f + 1 + nCol) << '\n';
    for (int i = 2; i <= nCol; ++i) {
        calc(1, nCol, 1, nCol);
        for (int i = 1; i <= nCol; ++i) g[i] = f[i];
        cout << *max_element(f + 1, f + 1 + nCol) << '\n';
    }
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	init(); process();
	return 0;
}

Compilation message

nafta.cpp: In function 'void calc(int, int, int, int)':
nafta.cpp:92:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |     int mid = l + r >> 1;
      |               ~~^~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16732 KB Output is correct
2 Correct 2 ms 16732 KB Output is correct
3 Correct 2 ms 16732 KB Output is correct
4 Correct 2 ms 16732 KB Output is correct
5 Correct 2 ms 16852 KB Output is correct
6 Correct 2 ms 16732 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16732 KB Output is correct
2 Correct 2 ms 16732 KB Output is correct
3 Correct 2 ms 16732 KB Output is correct
4 Correct 2 ms 16732 KB Output is correct
5 Correct 2 ms 16852 KB Output is correct
6 Correct 2 ms 16732 KB Output is correct
7 Correct 7 ms 23132 KB Output is correct
8 Correct 8 ms 23116 KB Output is correct
9 Correct 8 ms 23128 KB Output is correct
10 Correct 7 ms 23132 KB Output is correct
11 Correct 6 ms 23208 KB Output is correct
12 Correct 7 ms 23132 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16732 KB Output is correct
2 Correct 2 ms 16732 KB Output is correct
3 Correct 2 ms 16732 KB Output is correct
4 Correct 2 ms 16732 KB Output is correct
5 Correct 2 ms 16852 KB Output is correct
6 Correct 2 ms 16732 KB Output is correct
7 Correct 7 ms 23132 KB Output is correct
8 Correct 8 ms 23116 KB Output is correct
9 Correct 8 ms 23128 KB Output is correct
10 Correct 7 ms 23132 KB Output is correct
11 Correct 6 ms 23208 KB Output is correct
12 Correct 7 ms 23132 KB Output is correct
13 Correct 240 ms 108352 KB Output is correct
14 Correct 293 ms 108384 KB Output is correct
15 Correct 264 ms 108116 KB Output is correct
16 Correct 196 ms 108164 KB Output is correct
17 Correct 212 ms 108112 KB Output is correct
18 Correct 212 ms 108372 KB Output is correct