oj.uz

Submission #852321

# Submission time Handle Problem Language Result Execution time Memory
852321 2023-09-21T15:16:11 Z vjudge1 Nafta (COI15_nafta) C++17
100 / 100
 364 ms 103228 KB 
#include <iostream>
#include <vector>
using namespace std;
int n, m, a[2005][2005], dd[2005][2005], f[2005][2005], ma = 0, mi = 999999999, c = 0;
int d[2005], res[2005], ff[2005][2005];
vector<pair<int, int>> g[2005];
void dfs(int x, int y) {
    if (x < 1 || y < 1 || x > n || y > m || a[x][y] == -1 || dd[x][y] == 1) return;
    dd[x][y] = 1;
    ma = max(ma, y);
    mi = min(mi, y);
    c += a[x][y];
    dfs(x - 1, y);
    dfs(x + 1, y);
    dfs(x, y - 1);
    dfs(x, y + 1);
}
void solve(int k, int l, int r, int x, int y) {
    if (l > r) return;
    int mid = (l + r) / 2, ma = 0, h = 0;
    for (int i = x; i <= min(mid, y); i++) {
        if (f[i][k - 1] - ff[i][mid] >= ma) {
            ma = f[i][k - 1] - ff[i][mid];
            h = i;
        }
    }
    f[mid][k] = ma + f[mid][1];
    res[k] = max(res[k], f[mid][k]);
    solve(k, l, mid - 1, x, h);
    solve(k, mid + 1, r, h, y);
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            char x;
            cin >> x;
            if (x == '.') a[i][j] = -1;
            else a[i][j] = x - '0';
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (dd[i][j] == 0 && a[i][j] != -1) {
                c = ma = 0;
                mi = 999999999;
                dfs(i, j);
                g[mi].push_back({mi, c});
                g[ma + 1].push_back({mi, -c});
                for (int k = mi; k <= ma; k++) {
                    f[k][1] += c;
                    res[1] = max(res[1], f[k][1]);
                }
            }
        }
    }
    for (int i = 1; i <= m; i++) {
        for (auto w : g[i]) {
            d[w.first] += w.second;
        }
        int h = 0;
        for (int j = 1; j <= i; j++) {
            h += d[j];
            ff[j][i] = h;
        }
    }
    cout << res[1] << '\n';
    for (int i = 2; i <= m; i++) {
        solve(i, 1, n, 1, n);
        cout << res[i] << '\n';
    }
}

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8792 KB Output is correct
2 Correct 1 ms 8792 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 1 ms 8796 KB Output is correct
5 Correct 2 ms 8792 KB Output is correct
6 Correct 2 ms 8792 KB Output is correct
7 Correct 8 ms 15708 KB Output is correct
8 Correct 9 ms 15448 KB Output is correct
9 Correct 9 ms 16216 KB Output is correct
10 Correct 7 ms 14680 KB Output is correct
11 Correct 7 ms 14680 KB Output is correct
12 Correct 6 ms 14684 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8792 KB Output is correct
2 Correct 1 ms 8792 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 1 ms 8796 KB Output is correct
5 Correct 2 ms 8792 KB Output is correct
6 Correct 2 ms 8792 KB Output is correct
7 Correct 8 ms 15708 KB Output is correct
8 Correct 9 ms 15448 KB Output is correct
9 Correct 9 ms 16216 KB Output is correct
10 Correct 7 ms 14680 KB Output is correct
11 Correct 7 ms 14680 KB Output is correct
12 Correct 6 ms 14684 KB Output is correct
13 Correct 310 ms 77904 KB Output is correct
14 Correct 334 ms 70856 KB Output is correct
15 Correct 364 ms 103228 KB Output is correct
16 Correct 286 ms 66236 KB Output is correct
17 Correct 265 ms 60128 KB Output is correct
18 Correct 263 ms 60600 KB Output is correct