제출 #539365

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
539365		jesus_coconut	Bulldozer (JOI17_bulldozer)	C++17	100 / 100	1721 ms	99224 KiB

bulldozer

#include <bits/stdc++.h>
#define F first
#define S second
#define all(a) begin(a), end(a)
#define pb push_back
#define eb emplace_back
using namespace std;

using ll = long long;

using cll = complex<long long>;
using pii = pair<int, int>;

int n;
vector<pair<cll, ll>> v;

ll cross(cll a, cll b) {
    return (conj(a) * b).imag();
}

ll ccw(cll a, cll b, cll c) {
    return cross(b - a, c - b);
}

bool sign(cll a) {
    return a.imag() > 0 || (a.imag() == 0 && a.real() > 0);
}

vector<pair<cll, pair<int, int>>> events;

struct Item {
    ll mxPref = 0, mxSuf = 0, mxSuma = 0, suma = 0;
};

struct SegTree {
    int static const N = (1 << 11);
    array<Item, 2 * N> val;

    Item merg(Item a, Item b) {
        Item ret;
        ret.mxPref = max(a.mxPref, a.suma + b.mxPref);
        ret.mxSuf = max(b.mxSuf, b.suma + a.mxSuf);
        ret.suma = a.suma + b.suma;
        ret.mxSuma = max({a.mxSuma, b.mxSuma, a.mxSuf + b.mxPref});
        return ret;
    }

    void upd(int p, ll elem, int ver, int lx, int rx) {
        if (rx - lx == 1) {
            val[ver].mxPref = val[ver].mxSuf = val[ver].mxSuma = val[ver].suma = elem;
            return;
        }
        int mid = (lx + rx) / 2;
        if (p < mid) upd(p, elem, ver * 2 + 1, lx, mid);
        else upd(p, elem, ver * 2 + 2, mid, rx);
        val[ver] = merg(val[ver * 2 + 1], val[ver * 2 + 2]);
    }

    void upd(int p, ll elem) { upd(p, elem, 0, 0, N); }

    ll query() { return val[0].mxSuma; }
};

int pos[2010];

void solve() {
    cin >> n;
    v.resize(n);
    for (auto &[p, val] : v) {
        ll a, b;
        cin >> a >> b >> val;
        p.real(a);
        p.imag(b);
    }
    sort(all(v), [](auto const &a, auto const &b) {
        return a.F.real() < b.F.real() || (a.F.real() == b.F.real() && a.F.imag() > b.F.imag());
    });
    SegTree st;
    for (int i = 0; i < n; ++i) {
        st.upd(i, v[i].S);
    }
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            events.eb((v[j].F - v[i].F) * cll(0, 1), pii{i, j});
            events.eb((v[j].F - v[i].F) * cll(0, -1), pii{j, i});
        }
    }
    sort(all(events), [&](auto const &a, auto const &b) {
        if (sign(a.F) != sign(b.F)) return sign(a.F) > sign(b.F);
        ll c = ccw(cll(0, 0), a.F, b.F);
        if (c == 0) return a.S < b.S;
        return c > 0;
    });
    ll res = st.query();
    iota(pos, pos + n + 10, 0);
    for (int i = 0; i < size(events); ++i) {
        auto p = events[i].S;
        st.upd(pos[p.F], v[p.S].S);
        st.upd(pos[p.S], v[p.F].S);
        swap(pos[p.F], pos[p.S]);
        if (i + 1 < size(events) && ccw(cll(0, 0), events[i].F, events[i+1].F) == 0) continue;
        res = max(res, st.query());
    }
    cout << res << '\n';
}

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

    solve();


    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

bulldozer.cpp: In function 'void solve()':
bulldozer.cpp:96:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::complex<long long int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     for (int i = 0; i < size(events); ++i) {
      |                     ~~^~~~~~~~~~~~~~
bulldozer.cpp:101:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::complex<long long int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |         if (i + 1 < size(events) && ccw(cll(0, 0), events[i].F, events[i+1].F) == 0) continue;
      |             ~~~~~~^~~~~~~~~~~~~~

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