Submission #1302085

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302085		uranium235	Nafta (COI15_nafta)	C++17	34 / 100	109 ms	22440 KiB

nafta

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

template <class a, class b> ostream& operator<<(ostream &l, const pair<a, b> &r) {
    l << "(" << r.first << ", " << r.second << ")";
    return l;
}

template <class t, unsigned long int s> ostream& operator<<(ostream &l, const array<t, s> &r) {
    l << "[";
    for (int i = 0; i + 1 < s; i++) l << r[i] << ", ";
    if (s > 0) l << r[s - 1];
    l << "]";
    return l;
}

template <class t> ostream& operator<<(ostream &l, const vector<t> &r) {
    l << "{";
    for (int i = 0; i + 1 < r.size(); i++) l << r[i] << ", ";
    if (!r.empty()) l << r.back();
    l << "}";
    return l;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    vector<vector<int>> a(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            char c;
            cin >> c;
            a[i][j] = c == '.' ? -1 : (c - '0');
        }
    }

    vector<array<int, 3>> ints;
    array<array<int, 2>, 4> del{{ {0, 1}, {0, -1}, {1, 0}, {-1, 0} }};
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (a[i][j] == -1) continue;

            array<int, 3> x{{ j, j, 0 }};
            queue<pair<int, int>> q;
            q.push({i, j});
            while (!q.empty()) {
                pair<int, int> p = q.front();
                q.pop();
                if (a[p.first][p.second] == -1) continue;
                x[0] = min(x[0], p.second);
                x[1] = max(x[1], p.second);
                x[2] += a[p.first][p.second];
                a[p.first][p.second] = -1;

                for (auto [dx, dy] : del) {
                    dx += p.first;
                    dy += p.second;
                    if (dx < 0 || dx >= n || dy < 0 || dy >= m) continue;

                    q.push({dx, dy});
                }
            }

            ints.push_back(x);
        }
    }
    if (n > 300) return 0;
    sort(ints.begin(), ints.end());
    vector<array<int, 3>> aux = ints;
    sort(aux.begin(), aux.end(), [](const array<int, 3> &l, const array<int, 3> &r) -> bool {
        return l[1] < r[1];
    });

    vector<vector<int>> c(m, vector<int>(m));
    for (int i = 0; i < m; i++) {
        int ptr = 0, rtp = 0, cur = 0;
        for (int j = i; j < m; j++) {
            while (ptr < ints.size() && ints[ptr][0] <= j) {
                if (ints[ptr][0] > i - 1) cur += ints[ptr][2];
                ptr++;
            }
            while (rtp < aux.size() && aux[rtp][1] < j) {
                if (aux[rtp][0] > i - 1) cur -= aux[rtp][2];
                rtp++;
            }
            c[i][j] = cur;
        }
    }


    vector<int> dp(m + 1), pd(m + 1);
    auto dnc = [&](int l, int r, int ql, int qr, auto &&self) -> void {
        int m = (l + r) / 2;
        pair<int, int> cur;
        for (int i = ql; i <= min(qr, m); i++) {
            cur = max(cur, { dp[i] + c[i][m], i });
        }
        pd[m + 1] = cur.first;
        if (l == r) return;
        self(l, m, ql, cur.second, self);
        self(m + 1, r, cur.second, qr, self);
    };
    for (int i = 0; i < m; i++) {
        fill(pd.begin(), pd.end(), 0);
        dnc(0, m - 1, 0, m - 1, dnc);
        int mx = 0;
        for (int i : pd) mx = max(mx, i);
        cout << mx << '\n';
        swap(dp, pd);
    }
}

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