oj.uz

Submission #891809

# Submission time Handle Problem Language Result Execution time Memory
891809 2023-12-24T05:11:47 Z chanhchuong123 Nafta (COI15_nafta) C++14
100 / 100
 298 ms 104400 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 3 ms 16732 KB Output is correct
5 Correct 2 ms 16732 KB Output is correct
6 Correct 3 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 3 ms 16732 KB Output is correct
5 Correct 2 ms 16732 KB Output is correct
6 Correct 3 ms 16732 KB Output is correct
7 Correct 7 ms 23016 KB Output is correct
8 Correct 8 ms 23132 KB Output is correct
9 Correct 8 ms 23020 KB Output is correct
10 Correct 6 ms 23128 KB Output is correct
11 Correct 6 ms 23132 KB Output is correct
12 Correct 5 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 3 ms 16732 KB Output is correct
5 Correct 2 ms 16732 KB Output is correct
6 Correct 3 ms 16732 KB Output is correct
7 Correct 7 ms 23016 KB Output is correct
8 Correct 8 ms 23132 KB Output is correct
9 Correct 8 ms 23020 KB Output is correct
10 Correct 6 ms 23128 KB Output is correct
11 Correct 6 ms 23132 KB Output is correct
12 Correct 5 ms 23132 KB Output is correct
13 Correct 239 ms 104020 KB Output is correct
14 Correct 298 ms 104224 KB Output is correct
15 Correct 286 ms 104016 KB Output is correct
16 Correct 194 ms 104228 KB Output is correct
17 Correct 170 ms 104400 KB Output is correct
18 Correct 172 ms 104020 KB Output is correct