oj.uz

Submission #669876

# Submission time Handle Problem Language Result Execution time Memory
669876 2022-12-07T14:53:07 Z borisAngelov Nafta (COI15_nafta) C++11
100 / 100
 437 ms 120672 KB 
#include <iostream>
#include <utility>
#include <queue>
#include <tuple>

using namespace std;

const int maxn = 3005;

int n, m;
char table[maxn][maxn];

pair<int, int> dirs[4] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

int component_idx = 0;
int component[maxn][maxn];
int sum[maxn * maxn];
int left_end[maxn * maxn];
int right_end[maxn * maxn];
bool seen[maxn * maxn];

int dp[maxn][maxn];
int cost[maxn][maxn];
int interval[maxn];

void dfs(int x, int y) {
    component[x][y] = component_idx;

    for (int d = 0; d < 4; ++d) {
        int new_x = x + dirs[d].first;
        int new_y = y + dirs[d].second;

        if (new_x < 1 || new_x > n || new_y < 1 || new_y > m) continue;
        if (table[new_x][new_y] == '.' || component[new_x][new_y] != 0) continue;

        dfs(new_x, new_y);
    }
}

void divideAndConquer(int row, int l, int r, int optl, int optr) {
    if (l > r) return;

    int mid = (l + r) >> 1;

    int opt = -1;
    int bestValue = -1000000;

    for (int i = optl; i <= min(mid, optr); ++i) {
        if (dp[row - 1][i] + cost[i][mid] > bestValue) {
            bestValue = dp[row - 1][i] + cost[i][mid];
            opt = i;
        }
    }

    dp[row][mid] = bestValue;

    divideAndConquer(row, l, mid - 1, optl, opt);
    divideAndConquer(row, mid + 1, r, opt, optr);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m;

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> table[i][j];
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (component[i][j] == 0 && table[i][j] != '.') {
                component_idx++;
                dfs(i, j);
            }
        }
    }

    for (int i = 1; i <= component_idx; ++i) {
        left_end[i] = m + 1;
        right_end[i] = 0;
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (component[i][j] != 0) {
                sum[component[i][j]] += (table[i][j] - '0');
                left_end[component[i][j]] = min(left_end[component[i][j]], j);
                right_end[component[i][j]] = max(right_end[component[i][j]], j);
            }
        }
    }

    for (int j = 1; j <= m; ++j) {
        int current = 0;

        for (int i = 1; i <= n; ++i) {
            if (seen[component[i][j]] == false) {
                seen[component[i][j]] = true;
                interval[right_end[component[i][j]]] += sum[component[i][j]];
                current += sum[component[i][j]];
            }
        }

        for (int i = 1; i <= n; ++i) {
            seen[component[i][j]] = false;
        }

        for (int j1 = 0; j1 < j; ++j1) {
            cost[j1][j] += current;
        }

        int to_left = current - interval[j];

        for (int j1 = j + 1; j1 <= m; ++j1) {
            cost[j][j1] -= to_left;
            to_left -= interval[j1];
        }

        for (int i = 1; i <= m; ++i) {
            interval[i] = 0;
        }
    }

    for (int i = 1; i <= m; ++i) {
        divideAndConquer(i, 1, n, 0, n);

        for (int j = 1; j <= n; ++j) {
            dp[i][j] = max(dp[i][j], dp[i][j - 1]);
        }
    }

    for (int i = 1; i <= m; ++i) {
        cout << dp[i][n] << "\n";
    }

    return 0;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 8 ms 5972 KB Output is correct
8 Correct 9 ms 5908 KB Output is correct
9 Correct 10 ms 6996 KB Output is correct
10 Correct 7 ms 5076 KB Output is correct
11 Correct 7 ms 5076 KB Output is correct
12 Correct 6 ms 5052 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 8 ms 5972 KB Output is correct
8 Correct 9 ms 5908 KB Output is correct
9 Correct 10 ms 6996 KB Output is correct
10 Correct 7 ms 5076 KB Output is correct
11 Correct 7 ms 5076 KB Output is correct
12 Correct 6 ms 5052 KB Output is correct
13 Correct 354 ms 76084 KB Output is correct
14 Correct 401 ms 76368 KB Output is correct
15 Correct 437 ms 120672 KB Output is correct
16 Correct 305 ms 64600 KB Output is correct
17 Correct 312 ms 61656 KB Output is correct
18 Correct 308 ms 61464 KB Output is correct