Submission #704825

#	Time	Username	Problem	Language	Result	Execution time	Memory
704825		kelfert	Nafta (COI15_nafta)	C++17	34 / 100	1075 ms	53140 KiB

nafta

#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

#define all(x) (x).begin(), (x).end()
typedef long long ll;

const int INF = 2e9;
const int N = 2001;

int cost[N][N], used[N][N], a[N][N], dp[N][N], cnt2[N];
int opt, mid; 

void divide(int j, int l, int r, int ql, int qr) {
    if (l >= r) return;
    mid = (l + r) / 2;
    for (int i = ql; i < min(mid, qr); i++) {
        if (dp[j][mid] < dp[j - 1][i] + cost[i][mid]) {
            dp[j][mid] = dp[j - 1][i] + cost[i][mid];
            opt = i;
        }
    }
    divide(j, l, mid, ql, opt + 1);
    divide(j, mid + 1, r, opt, qr);
}

int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

void dfs(int vx, int vy, int &sum, int &l, int &r) {
    used[vx][vy] = 1;
    sum += a[vx][vy];
    l = min(l, vy);
    r = max(r, vy);
    for (int k = 0; k < 4; k++) {
        int x = vx + dx[k], y = vy + dy[k];
        if (!used[x][y] && a[x][y] != -1) {
            dfs(x, y, sum, l, r);
        }
    }
} 

const int OPEN = 1;
const int CLOSE = -1;

struct Event {
    int x, id, tp, sum;
    Event(int x, int id, int tp, int sum) : x(x), id(id), tp(tp), sum(sum) {}
    Event() {}
};

bool comp(Event a, Event b) {
    return a.x < b.x;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m; cin >> n >> m;
    for (int i = 0; i <= n + 1; i++)
        for (int j = 0; j <= m + 1; j++)
            a[i][j] = -1;
    string s;
    for (int i = 1; i <= n; i++) {
        cin >> s;
        for (int j = 0; j < m; j++)
            if (s[j] != '.') a[i][j + 1] = (s[j] - '0');
    }
    vector<int> seg;
    vector<Event> events;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (!used[i][j] && a[i][j] != -1) {
                int sum = 0, l = j, r = j;
                dfs(i, j, sum, l, r);
                seg.push_back(l);
                events.push_back(Event(l, seg.size() - 1, OPEN, sum));
                events.push_back(Event(r, seg.size() - 1, CLOSE, sum));
            }
        }
    }
    sort(all(events), comp);
    for (auto x : events) {
        if (x.tp == OPEN) cnt2[x.x] += x.sum;
    }
    int first = 0, sz = events.size();
    for (int l = 0; l <= m; l++) {
        while (first < sz && events[first].x <= l) first++;
        int i = first, sum = 0;
        for (int r = l + 1; r <= m; r++) {
            while (i < sz && events[i].x < r) {
                if (events[i].tp == OPEN) sum += events[i].sum;
                else if (seg[events[i].id] > l) sum -= events[i].sum;
                i++;    
            }
            cost[l][r] = sum + cnt2[r];
        }
    }
    int ans = 0;
    for (int j = 1; j <= m; j++) {
        divide(j, 0, m + 1, 0, m + 1);
        ans = 0;
        for (int i = 1; i <= m; i++) ans = max(ans, dp[j][i]);
        cout << ans << "\n";
    }
    
    return 0;
}

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