Submission #852321

#	Time	Username	Problem	Language	Result	Execution time	Memory
852321		vjudge1	Nafta (COI15_nafta)	C++17	100 / 100	364 ms	103228 KiB

nafta

#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 / 11
• Subtask 2: 23 / 23
• Subtask 3: 66 / 66