Submission #1257898

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257898		bbldrizzy	Nafta (COI15_nafta)	C++20	100 / 100	437 ms	100960 KiB

nafta

#include <bits/stdc++.h>
#include <ios>
#include <iostream>
#include <random>
using namespace std;
using ll = long long;
using P = pair<int, int>;
#define f first
#define s second
const int MOD = 1e9+7;
const ll inf = 4*1e18;
const int mx = 5*1e5+5;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int sum = 0;
int l = 1e9;
int R = 0;
int r, c; 
vector<vector<bool>> vis;
vector<vector<int>> cost;

bool inbounds(int x, int y) {
    return x >= 0 && x < r && y >= 0 && y < c;
}

void dfs(int x, int y, vector<vector<char>> &g) {
    vis[x][y] = true;
    sum += (g[x][y]-'0');
    l = min(l, y);
    R = max(R, y);
    for (int i = 0; i < 4; i++) {
        int xd = x+dx[i]; int yd = y+dy[i];
        if (inbounds(xd, yd) && !vis[xd][yd]) {
            dfs(xd, yd, g);
        }
    }
}

vector<vector<int>> dp;
void solve(ll id, ll i, ll j, ll le, ll ri) {
    if (i > j) return;
    ll mid = (i+j)/2;
    ll mn = 0;
    ll best = le;
    for (ll k = le; k <= min(mid, ri); k++) {
        ll v = dp[k-1][id-1] + cost[k-1][mid];
        if (v > mn) {
            best = k;
            mn = v;
        }
    }
    dp[mid][id] = mn;
    solve(id, i, mid-1, le, best);
    solve(id, mid+1, j, best, ri);
}

int main() {
    cin >> r >> c;
    vector<vector<char>> g(r, vector<char>(c, '.'));
    vis.resize(r, vector<bool>(c));
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            char c; cin >> c;
            g[i][j] = c;
            if (g[i][j] == '.') vis[i][j] = true;
        }
    }
    vector<vector<pair<int, int>>> start(c+1);
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (!vis[i][j]) {
                // cout << "i, j: " << i << ", " << j << "\n";
                sum = 0;
                l = 1e9;
                R = 0;
                dfs(i, j, g);
                start[R+1].push_back({l+1, sum});
                // cout << "l, R, sum: " << l <<  ", " << R << ", " << sum << "\n";
            }
        }
    }
    cost.resize(c+1, vector<int>(c+1));
    vector<int> W(c+1, 0);
    for (int rr = 1; rr <= c; ++rr) {
        for (auto &pr : start[rr]) {
            W[pr.first] += pr.second;
        }
    }
    vector<int> P(c+1, 0);
    for (int j = 1; j <= c; j++) {
        P[0] = 0;
        for (int x = 1; x <= c; x++) P[x] = P[x-1]+W[x];
        for (int i = 0; i < j; i++) {
            cost[i][j] = P[j]-P[i];
        }
        for (auto &pr: start[j]) {
            W[pr.first] -= pr.second;
        }
    }
    dp.assign(c+1, vector<int>(c+1));
    int mx = 0;
    for (int i = 1; i <= c; i++) {
        dp[i][1] = cost[0][i];
        mx = max(dp[i][1], mx);
        // cout << dp[i][1] << "\n";
    }
    cout << mx << "\n";
    for (int i = 2; i <= c; i++) {
        solve(i, 1, c, 1, c);
        mx = 0;
        for (int j = 1; j <= c; j++) {
            mx = max(mx, dp[j][i]);
        }
        cout << mx << "\n";
    }
}

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