Submission #897358

#	Time	Username	Problem	Language	Result	Execution time	Memory
897358		box	Bulldozer (JOI17_bulldozer)	C++17	100 / 100	637 ms	63396 KiB

bulldozer

#include <algorithm>
#include <array>
#include <iostream>
#include <numeric>
using namespace std;
    
#define ar array
#define ll long long
    
const int N = 2e3, N_ = 1 << 11;
    
ar<int, 2> norm(ar<int, 2> a) {
    int g = gcd(a[0], a[1]);
    a[0] /= g, a[1] /= g;
    if (a[1] < 0)
        a[0] *= -1, a[1] *= -1;
    return a;
}
bool comp(const ar<int, 2>& a, const ar<int, 2>& b) {
    return 1LL * a[0] * b[1] < 1LL * b[0] * a[1];
}
    
ar<ll, 4> operator+(const ar<ll, 4>& u, const ar<ll, 4>& v) {
    return {u[0] + v[0], max(u[1], u[0] + v[1]), max(v[2], u[2] + v[0]), max(u[2] + v[1], max(u[3], v[3]))};
}
    
int n_;
ar<ll, 4> t[N_ * 2];
    
void update(int i, int w) {
    t[i += n_] = {w, max(0, w), max(0, w), max(0, w)};
    while (i >>= 1)
        t[i] = t[i << 1 | 0] + t[i << 1 | 1];
}
    
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n;
    cin >> n;
    n_ = 1;
    while (n_ < n)
        n_ <<= 1;
    static ar<int, 3> p[N];
    for (int i = 0; i < n; i++) {
        auto &[x, y, w] = p[i];
        cin >> x >> y >> w;
    }
    sort(p, p + n);
    static pair<ar<int, 2>, ar<int, 2>> e[N * (N - 1) / 2];
    int m = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (p[i][0] != p[j][0])
                e[m++] = make_pair(norm({p[j][1] - p[i][1], p[j][0] - p[i][0]}), ar<int, 2>{i, j});
    stable_sort(e, e + m, [&](const pair<ar<int, 2>, ar<int, 2>>& a, const pair<ar<int, 2>, ar<int, 2>>& b) {
        return comp(a.first, b.first);
    });
    static int o[N];
    for (int i = 0; i < n; i++) {
        update(i, p[i][2]);
        o[i] = i;
    }
    ll ans = t[1][3];
    for (int h = 0; h < m; h++) {
        auto [s, ij] = e[h];
        auto [i, j] = ij;
        swap(o[i], o[j]);
        update(o[i], p[i][2]), update(o[j], p[j][2]);
        if (h == m - 1 || s != e[h + 1].first)
            ans = max(ans, t[1][3]);
    }
    cout << ans << '\n';
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 20 / 20
• Subtask 3: 35 / 35
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20