oj.uz

Submission #852320

# Submission time Handle Problem Language Result Execution time Memory
852320 2023-09-21T15:16:00 Z adaawf Nafta (COI15_nafta) C++14
100 / 100
 380 ms 107092 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 8796 KB Output is correct
2 Correct 1 ms 8792 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 1 ms 8796 KB Output is correct
6 Correct 1 ms 8796 KB Output is correct

Subtask #2
23.0 / 23.0

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

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8796 KB Output is correct
2 Correct 1 ms 8792 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 1 ms 8796 KB Output is correct
6 Correct 1 ms 8796 KB Output is correct
7 Correct 8 ms 15708 KB Output is correct
8 Correct 9 ms 15708 KB Output is correct
9 Correct 10 ms 16216 KB Output is correct
10 Correct 8 ms 14924 KB Output is correct
11 Correct 7 ms 14680 KB Output is correct
12 Correct 7 ms 14684 KB Output is correct
13 Correct 313 ms 81244 KB Output is correct
14 Correct 345 ms 74716 KB Output is correct
15 Correct 380 ms 107092 KB Output is correct
16 Correct 286 ms 69836 KB Output is correct
17 Correct 257 ms 64088 KB Output is correct
18 Correct 254 ms 64340 KB Output is correct