oj.uz

Submission #669869

# Submission time Handle Problem Language Result Execution time Memory
669869 2022-12-07T14:40:10 Z borisAngelov Nafta (COI15_nafta) C++11
34 / 100
 1000 ms 64812 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);
    }
}

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 <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            dp[i][j] = dp[i - 1][j];

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

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

    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1104 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 1 ms 968 KB Output is correct
5 Correct 1 ms 976 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 1 ms 1108 KB Output is correct
2 Correct 1 ms 1104 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 1 ms 968 KB Output is correct
5 Correct 1 ms 976 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 22 ms 5904 KB Output is correct
8 Correct 23 ms 5824 KB Output is correct
9 Correct 23 ms 6980 KB Output is correct
10 Correct 21 ms 5196 KB Output is correct
11 Correct 21 ms 4940 KB Output is correct
12 Correct 23 ms 5280 KB Output is correct

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1104 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 1 ms 968 KB Output is correct
5 Correct 1 ms 976 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 22 ms 5904 KB Output is correct
8 Correct 23 ms 5824 KB Output is correct
9 Correct 23 ms 6980 KB Output is correct
10 Correct 21 ms 5196 KB Output is correct
11 Correct 21 ms 4940 KB Output is correct
12 Correct 23 ms 5280 KB Output is correct
13 Execution timed out 1020 ms 64812 KB Time limit exceeded
14 Halted 0 ms 0 KB -