Submission #1250516

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250516		_filya_	Nafta (COI15_nafta)	C++20	100 / 100	307 ms	173604 KiB

nafta

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;

const int N = 2001;

ll dp[N][N], w[N][N], c[N], n, m;
bool vis[N][N];
string g[N];
vector<array<ll, 3>> seg;

void dfs(int x, int y, int& l, int& r, ll& sum) {
    if (g[x][y] == '.' || vis[x][y]) return;
    vis[x][y] = 1;
    l = min(l, y);
    r = max(r, y);
    sum += g[x][y] - '0';
    if (x) {
        dfs(x - 1, y, l, r, sum);
    }
    if (x < n - 1) {
        dfs(x + 1, y, l, r, sum);
    }
    if (y) {
        dfs(x, y - 1, l, r, sum);
    }
    if (y < m - 1) {
        dfs(x, y + 1, l, r, sum);
    }
}

int main()
{
// 	ifstream cin("input.txt");
//     ofstream cout("output.txt");
	ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> g[i];
	for (int x = 0; x < n; x++) for (int y = 0; y < m; y++) {
        int l = n, r = 0;
        ll sum = 0;
        dfs(x, y, l, r, sum);
        if (!sum) continue;
        seg.push_back({l, r, sum});
    } 

    vector<ll> scan(m + 1, 0);
    for (auto u : seg) {
        scan[u[0]] += u[2];
        scan[u[1] + 1] -= u[2];
    }
    ll cc = 0;
    for (int i = 0; i < m; i++) {
        cc += scan[i];
        c[i + 1] = cc;
    }

    vector<vector<pair<ll, ll>>> segl(m + 1);
    vector<vector<ll>> segrl(m + 1, vector<ll>(m + 1, 0));
    for (auto s : seg) {
        segl[s[0] + 1].push_back({s[1] + 1, s[2]});
        segrl[s[0] + 1][s[1] + 1] += s[2];
    }
    for (int i = 0; i <= m; i++) sort(segl[i].begin(), segl[i].end());
    for (int j = 0; j <= m; j++) for (int i = segl[j].size() - 2; i >= 0; i--) {
        segl[j][i].second += segl[j][i + 1].second;
    }
    for (int len = 1; len <= m; len++) for (int l = m - len + 1; l >= 0; l--) {
        int r = l + len - 1;
        if (len == 1) {
            w[l][r] = c[l];
            continue;
        }
        int low = -1, high = segl[l + 1].size();
        while(high - low > 1) {
            int mid = (high + low + 1) / 2;
            if (segl[l + 1][mid].first >= r) {
                high = mid;
            } else {
                low = mid;
            }
        }
        w[l][r] = w[l + 1][r] - (high == segl[l + 1].size() ? 0 : segl[l + 1][high].second);
    }

    for (int i = 0; i <= m; i++) dp[0][i] = 0;
    auto solve = [&](auto&& self, int ki, int l, int r, int cl, int cr) -> void {
        if (l >= r) return;
        int mid = (r + l) / 2, opt;
        dp[ki][mid] = 0;
        for (int i = cl; i <= min(cr, mid); i++) {
            if (dp[ki][mid] < dp[ki - 1][i] + c[mid] - w[i][mid]) {
                dp[ki][mid] = dp[ki - 1][i] + c[mid] - w[i][mid];
                opt = i;
            }
        }
        self(self, ki, l, mid, cl, opt);
        self(self, ki, mid + 1, r, opt, cr);
    };

    for (int ki = 1; ki <= m; ki++) {
        solve(solve, ki, 0, m + 1, 0, m + 1);
        ll ans = 0;
        for (int i = 1; i <= m; i++) {
            ans = max(ans, dp[ki][i]);
        }
        cout << ans << '\n';
    }
}

• Subtask 1: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 66 / 66