Submission #1222055

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222055		395333em	Nafta (COI15_nafta)	C++20	100 / 100	383 ms	76452 KiB

nafta

#include <bits/stdc++.h>
#define int long long
#define emb emplace_back
#define pii pair <int, int>

using namespace std;

const int mod = 1e9 + 7;
const int inf = 1e18;
const int N = 2e3 + 5;

int n, m, dp[N][N], cal[N][N]; // dp[i][j] = max number of oil after picking i columns including column j
char a[N][N];
bool visited[N][N];
map <int, vector <pii>> mp;

struct fenwick {
    int fw[N];
    void update(int idx, int val){
        if (idx >= N) return;
        fw[idx] += val;
        update(idx + (idx & -idx), val);
    }
    int query(int idx){
        if (idx <= 0) return 0;
        return fw[idx] + query(idx - (idx & -idx));
    }
} f;

void bfs(int r, int c){
    queue <pii> q; q.emplace(r, c);
    int sum = 0;
    int dx[] = {1, 0, -1, 0};
    int dy[] = {0, 1, 0, -1};
    visited[r][c] = true;
    int mn = inf, mx = 0;
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        sum += a[x][y] - '0';
        mn = min(mn, y);
        mx = max(mx, y);
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 1 || nx > n || ny < 1 || ny > m || a[nx][ny] == '.' || visited[nx][ny]) continue;
            visited[nx][ny] = true;
            q.emplace(nx, ny);
        }
    }
    mp[mx].emb(mn, sum);
    // cout << mn << " -> " << mx << ": " << sum << "\n";
}

void recur(int l, int r, int left, int right, int lv){
    if (r < l) return;
    int mid = (l + r) / 2;
    pii ans = {-inf, 0};
    for (int i = left; i <= min(mid, right); i++) {
        ans = max(ans, {dp[lv - 1][i] + cal[mid][mid] - cal[i][mid], i});
    }
    dp[lv][mid] = ans.first;
    recur(l, mid - 1, left, ans.second, lv);
    recur(mid + 1, r, ans.second, right, lv);
}

signed main(){
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> a[i][j];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i][j] == '.' || visited[i][j]) continue;
            bfs(i, j);
        }
    }
    for (int r = m; r >= 1; r--) {
        for (auto [l, sum] : mp[r]) f.update(l, sum);
        for (int l = r; l >= 1; l--) cal[l][r] = f.query(l);
    }
    // cout << "----------------------------\n";
    // for (int i = 1; i <= m; i++) {
    //     for (int j = i + 1; j <= m; j++) {
    //         cout << i << " -> " << j << ": " << cal[i][j] << "\n";
    //     }
    // }
    for (int i = 1; i <= m; i++) dp[1][i] = cal[i][i];
    for (int k = 2; k <= m; k++) recur(1, m, 1, m, k);
    for (int i = 1; i <= m; i++) cout << *max_element(dp[i] + 1, dp[i] + 1 + m) << "\n";
}

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