oj.uz

Submission #328416

# Submission time Handle Problem Language Result Execution time Memory
328416 2020-11-16T13:03:41 Z dolphingarlic Nafta (COI15_nafta) C++14
34 / 100
 1000 ms 24396 KB 
#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());

    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.0 / 11.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 620 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 4 ms 620 KB Output is correct
5 Correct 2 ms 620 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 693 ms 2024 KB Output is correct
8 Correct 377 ms 1964 KB Output is correct
9 Correct 51 ms 3712 KB Output is correct
10 Correct 465 ms 1964 KB Output is correct
11 Correct 137 ms 1900 KB Output is correct
12 Correct 51 ms 1644 KB Output is correct

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 620 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 4 ms 620 KB Output is correct
5 Correct 2 ms 620 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 693 ms 2024 KB Output is correct
8 Correct 377 ms 1964 KB Output is correct
9 Correct 51 ms 3712 KB Output is correct
10 Correct 465 ms 1964 KB Output is correct
11 Correct 137 ms 1900 KB Output is correct
12 Correct 51 ms 1644 KB Output is correct
13 Execution timed out 1088 ms 24396 KB Time limit exceeded
14 Halted 0 ms 0 KB -