Submission #328417

#	Time	Username	Problem	Language	Result	Execution time	Memory
328417		dolphingarlic	Nafta (COI15_nafta)	C++14	34 / 100	705 ms	20460 KiB

nafta

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int n, m;
char grid[2001][2001];
bool visited[2001][2001];
int dx[4]{1, -1, 0, 0}, dy[4]{0, 0, 1, -1};
int dp[2001], segtree[8001], lazy[8001];

bool inside(int x, int y) {
    return x && y && x <= n && y <= m && !visited[x][y] && grid[x][y] != '.';
}

tuple<int, int, int> get_oil(int x, int y) {
    tuple<int, int, int> ret = {y, y, grid[x][y] - '0'};
    visited[x][y] = true;
    for (int i = 0; i < 4; i++) if (inside(x + dx[i], y + dy[i])) {
        tuple<int, int, int> pot = get_oil(x + dx[i], y + dy[i]);
        get<0>(ret) = min(get<0>(ret), get<0>(pot));
        get<1>(ret) = max(get<1>(ret), get<1>(pot));
        get<2>(ret) += get<2>(pot);
    }
    return ret;
}

void push_lazy(int node, int l, int r) {
    segtree[node] += lazy[node];
    if (l != r) {
        lazy[node * 2] += lazy[node];
        lazy[node * 2 + 1] += lazy[node];
    }
    lazy[node] = 0;
}

void build(int node = 1, int l = 0, int r = m) {
    lazy[node] = 0;
    if (l == r) segtree[node] = dp[l];
    else {
        int mid = (l + r) / 2;
        build(node * 2, l, mid);
        build(node * 2 + 1, mid + 1, r);
        segtree[node] = max(segtree[node * 2], segtree[node * 2 + 1]);
    }
}

int query(int pos, int node = 1, int l = 0, int r = m) {
    if (lazy[node]) push_lazy(node, l, r);
    if (l > pos) return 0;
    if (r <= pos) return segtree[node];
    int mid = (l + r) / 2;
    return max(query(pos, node * 2, l, mid), query(pos, node * 2 + 1, mid + 1, r));
}

void update(int pos, int val, int node = 1, int l = 0, int r = m) {
    if (lazy[node]) push_lazy(node, l, r);
    if (l > pos) return;
    if (r <= pos) {
        lazy[node] = val;
        push_lazy(node, l, r);
    } else {
        int mid = (l + r) / 2;
        update(pos, val, node * 2, l, mid);
        update(pos, val, node * 2 + 1, mid + 1, r);
        segtree[node] = max(segtree[node * 2], segtree[node * 2 + 1]);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
        cin >> grid[i][j];
    }
    vector<tuple<int, int, int>> oil;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
        if (inside(i, j)) {
            int l, r, val;
            tie(l, r, val) = get_oil(i, j);
            oil.push_back({l, l, val});
            oil.push_back({r + 1, l, -val});
        }
    }
    sort(oil.begin(), oil.end());

    if (n > 300) return 0;

    for (int _ = 1; _ <= m; _++) {
        memset(dp, 0, sizeof dp);
        for (int i = _, ptr = 0; i <= m; i++) {
            while (get<0>(oil[ptr]) <= i) {
                update(get<1>(oil[ptr]) - 1, get<2>(oil[ptr]));
                ptr++;
            }
            dp[i] = query(i - 1);
        }
        build();
        cout << query(m) << '\n';
    }
    return 0;
}

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