Submission #931862

#	Time	Username	Problem	Language	Result	Execution time	Memory
931862		Perl32	Bulldozer (JOI17_bulldozer)	C++14	100 / 100	956 ms	52172 KiB

bulldozer

//I wrote this code 4 u <3
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

struct Frac {
    ll p, q;

    Frac() {}
    Frac(ll p, ll q) : p(p), q(q) {}

    bool operator<(const Frac& oth) const {
        return p * oth.q < oth.p * q;
    }

    bool operator!=(const Frac& oth) const {
        return make_pair(p, q) != make_pair(oth.p, oth.q);
    }
};

struct Info {
    ll p = 0ll, s = 0ll, m = 0ll, a = 0ll;

    Info() = default;
    Info(ll v) {
        p = max(0ll, v);
        s = max(0ll, v);
        m = max(0ll, v);
        a = v;
    }
};

Info merge(Info& a, Info& b) {
    Info ret;
    ret.a = a.a + b.a;
    ret.p = max(a.p, a.a + b.p);
    ret.s = max(b.s, b.a + a.s);
    ret.m = max({a.m, b.m, a.s + b.p, ret.p, ret.s});
    return ret;
}

const int maxN = 1 << 11;
vector<Info> t(maxN * 4);
int sz;

void upd(int i, int v) {
    i += sz;
    t[i] = v;
    i >>= 1;
    while (i) {
        t[i] = merge(t[i << 1], t[i << 1 | 1]);
        i >>= 1;
    }
}

signed main(int32_t argc, char *argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    sz = 1;
    while (sz < n) sz <<= 1;
    vector<array<ll, 3>> kek(n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 3; ++j) {
            cin >> kek[i][j];
        }
    }
    sort(kek.begin(), kek.end());
    vector<tuple<Frac, int, int>> ev;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (kek[i][0] == kek[j][0]) continue;
            ll p = kek[j][1] - kek[i][1];
            ll q = kek[j][0] - kek[i][0];
            ll g = __gcd(p, q);
            p /= g, q /= g;
            if (q < 0) p *= -1, q *= -1;
            ev.emplace_back(Frac(p, q), i, j);
        }
    }
    sort(ev.begin(), ev.end());
    vector<int> ord(n);
    for (int i = 0; i < n; ++i) {
        ord[i] = i;
        upd(i, kek[i][2]);
    }
    ll ans = max(0ll, t[1].m);
    int m = (int) ev.size();
    for (int x = 0; x < m; ++x) {
        auto [s, i, j] = ev[x];
        swap(ord[i], ord[j]);
        upd(ord[i], kek[i][2]);
        upd(ord[j], kek[j][2]);
        if (x == m - 1 || s != get<0>(ev[x + 1]))
            ans = max(ans, t[1].m);
    }
    cout << ans;
}

/*

 */

Compilation message (stderr)

bulldozer.cpp: In function 'int main(int32_t, char**)':
bulldozer.cpp:99:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   99 |         auto [s, i, j] = ev[x];
      |              ^

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