oj.uz

Submission #539315

# Submission time Handle Problem Language Result Execution time Memory
539315 2022-03-18T17:10:24 Z jesus_coconut Bulldozer (JOI17_bulldozer) C++17
5 / 100
 4 ms 916 KB 
#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 inline cross(cll a, cll b) {
    return (conj(a) * b).imag();
}

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

bool inline 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].F) == 0) continue;
        res = max(res, st.query());
    }
    cout << res << '\n';
}

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

    solve();


    return 0;
}

Compilation message

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].F) == 0) continue;
      |             ~~~~~~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 916 KB Output is correct
2 Correct 3 ms 916 KB Output is correct
3 Correct 3 ms 916 KB Output is correct
4 Correct 3 ms 916 KB Output is correct
5 Correct 3 ms 916 KB Output is correct
6 Correct 3 ms 916 KB Output is correct
7 Correct 4 ms 916 KB Output is correct
8 Correct 3 ms 916 KB Output is correct
9 Correct 3 ms 916 KB Output is correct
10 Correct 4 ms 916 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 916 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 916 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 916 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 916 KB Output is correct
2 Correct 3 ms 916 KB Output is correct
3 Correct 3 ms 916 KB Output is correct
4 Correct 3 ms 916 KB Output is correct
5 Correct 3 ms 916 KB Output is correct
6 Correct 3 ms 916 KB Output is correct
7 Correct 4 ms 916 KB Output is correct
8 Correct 3 ms 916 KB Output is correct
9 Correct 3 ms 916 KB Output is correct
10 Correct 4 ms 916 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Incorrect 4 ms 916 KB Output isn't correct
17 Halted 0 ms 0 KB -