Submission #891806

#	Time	Username	Problem	Language	Result	Execution time	Memory
891806		chanhchuong123	Nafta (COI15_nafta)	C++14	100 / 100	293 ms	108384 KiB

nafta

#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 (stderr)

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 / 11
• Subtask 2: 23 / 23
• Subtask 3: 66 / 66