Submission #706284

#	Time	Username	Problem	Language	Result	Execution time	Memory
706284		bebra	Bulldozer (JOI17_bulldozer)	C++17	0 / 100	29 ms	336 KiB

bulldozer

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

#define dbg(x) cerr << #x << ": " << x << endl;


struct Point {
    ll x;
    ll y;
    ll cost;

    Point(ll _x = 0, ll _y = 0, ll _cost = 0) : x(_x), y(_y), cost(_cost) {}
};


struct Vec {
    ll x;
    ll y;

    Vec(ll _x = 0, ll _y = 0) : x(_x), y(_y) {}

    Vec(const Point& p1, const Point& p2) {
        x = p2.x - p1.x;
        y = p2.y - p1.y;
    }

    ll operator*(const Vec& other) const {
        return x * other.x + y * other.y;
    }

    ll operator^(const Vec& other) const {
        return x * other.y - other.x * y;
    }
};


struct Line {
    ll a;
    ll b;
    ll c;

    Line(ll _a = 0, ll _b = 0, ll _c = 0) : a(_a), b(_b), c(_c) {}

    Line(const Point& p1, const Point& p2) {
        a = p2.y - p1.y;
        b = p1.x - p2.x;
        c = p2.x * p1.y - p1.x * p2.y;
    }

    Line(const Line& line, const Point& p) {
        a = line.a;
        b = line.b;
        c = -p.x * a - p.y * b;
    }

    Line get_orthogonal() const {
        return {-b, a, c};
    }

    ll get(const Point& p) {
        return a * p.x + b * p.y + c;
    }
};


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

    int n;
    cin >> n;

    ll ans = 0;

    vector<Point> points(n);
    for (auto& [x, y, cost] : points) {
        cin >> x >> y >> cost;
        ans = max(ans, cost);
    }

    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            Line line(points[i], points[j]);
            // sorting by distance to the line
            vector<vector<Point>> a(2);
            ans = max(ans, points[i].cost + points[j].cost);
            for (const auto& p : points) {
                if (line.get(p) > 0) {
                    a[0].push_back(p);
                } else if (line.get(p) < 0) {
                    a[1].push_back(p);
                }
            }
            for (int t = 0; t <= 1; ++t) {
                sort(a[t].begin(), a[t].end(), [&](const auto& p1, const auto& p2) {
                    return abs(line.get(p1)) < abs(line.get(p2));
                });
                ll pref = 0;
                for (const auto& p : a[t]) {
                    pref += p.cost;
                    ans = max(ans, max(0LL, points[i].cost + points[j].cost) + pref);
                }
            }

        }
    }
    cout << ans << '\n';

    return 0;
}

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