Submission #706262

#	Time	Username	Problem	Language	Result	Execution time	Memory
706262		bebra	Bulldozer (JOI17_bulldozer)	C++17	0 / 100	415 ms	308 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(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;

        a *= -1;
        b *= -1;
        c *= -1;
    }


    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;

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

    auto sign = [&](ll value) {
        if (value < 0) return -1;
        return 1;
    };

    ll ans = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            Line line1(points[i], points[j]);
            for (int k = 0; k < n; ++k) {
                Line line2(line1, points[k]);
                ll curr_ans = 0;
                for (const auto& p : points) {
                    if (line1.get(p) == 0) {
                        curr_ans += p.cost;
                        continue;
                    }
                    if (line2.get(p) == 0) {
                        curr_ans += p.cost;
                        continue;
                    }
                    if (sign(line1.get(p)) == sign(line2.get(p))) {
                        curr_ans += p.cost;
                    }
                }
                ans = max(ans, curr_ans);
            }
        }
    }
    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