oj.uz

Submission #706310

# Submission time Handle Problem Language Result Execution time Memory
706310 2023-03-06T09:20:02 Z bebra Bulldozer (JOI17_bulldozer) C++17
0 / 100
 855 ms 364 KB 
#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;
    }
};

mt19937 rng(random_device{}());


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 t = 0; t <= 200; ++t) {
        int x = rng() % 100000000;
        if (rng() % 2) x *= -1;
        int y = rng() % 100000000;
        if (rng() % 2) x *= -1;
        points.emplace_back(x, y, 0);
    }

    n = points.size();

    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            Line line(points[i], points[j]);
            ll c = points[i].cost + points[j].cost;
            // 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);
                }
            }
            vector<ll> max_pref(2);
            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 = c;
                ll min_pref = min(0LL, pref);
                max_pref[t] = pref;
                for (const auto& p : a[t]) {
                    pref += p.cost;
                    min_pref = min(min_pref, pref);
                    max_pref[t] = max(max_pref[t], pref);
                    ans = max(ans, pref - min_pref);
                }
            }
            ans = max(ans, max_pref[0] + max_pref[1] - c);
        }
    }
    cout << ans << '\n';

    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 757 ms 340 KB Output is correct
2 Correct 787 ms 344 KB Output is correct
3 Correct 764 ms 344 KB Output is correct
4 Correct 760 ms 340 KB Output is correct
5 Correct 738 ms 364 KB Output is correct
6 Correct 730 ms 352 KB Output is correct
7 Correct 771 ms 344 KB Output is correct
8 Correct 742 ms 348 KB Output is correct
9 Correct 734 ms 348 KB Output is correct
10 Correct 772 ms 344 KB Output is correct
11 Correct 242 ms 340 KB Output is correct
12 Correct 266 ms 340 KB Output is correct
13 Correct 246 ms 340 KB Output is correct
14 Correct 247 ms 348 KB Output is correct
15 Incorrect 245 ms 340 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 795 ms 340 KB Output is correct
2 Correct 831 ms 344 KB Output is correct
3 Correct 794 ms 340 KB Output is correct
4 Correct 828 ms 340 KB Output is correct
5 Correct 855 ms 340 KB Output is correct
6 Correct 823 ms 344 KB Output is correct
7 Correct 821 ms 340 KB Output is correct
8 Correct 781 ms 344 KB Output is correct
9 Correct 774 ms 340 KB Output is correct
10 Correct 810 ms 344 KB Output is correct
11 Correct 247 ms 340 KB Output is correct
12 Correct 242 ms 212 KB Output is correct
13 Correct 247 ms 340 KB Output is correct
14 Correct 246 ms 340 KB Output is correct
15 Correct 250 ms 340 KB Output is correct
16 Correct 246 ms 340 KB Output is correct
17 Correct 244 ms 340 KB Output is correct
18 Correct 249 ms 320 KB Output is correct
19 Correct 279 ms 340 KB Output is correct
20 Correct 244 ms 324 KB Output is correct
21 Correct 756 ms 344 KB Output is correct
22 Correct 773 ms 340 KB Output is correct
23 Correct 753 ms 340 KB Output is correct
24 Correct 794 ms 344 KB Output is correct
25 Incorrect 807 ms 340 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 795 ms 340 KB Output is correct
2 Correct 831 ms 344 KB Output is correct
3 Correct 794 ms 340 KB Output is correct
4 Correct 828 ms 340 KB Output is correct
5 Correct 855 ms 340 KB Output is correct
6 Correct 823 ms 344 KB Output is correct
7 Correct 821 ms 340 KB Output is correct
8 Correct 781 ms 344 KB Output is correct
9 Correct 774 ms 340 KB Output is correct
10 Correct 810 ms 344 KB Output is correct
11 Correct 247 ms 340 KB Output is correct
12 Correct 242 ms 212 KB Output is correct
13 Correct 247 ms 340 KB Output is correct
14 Correct 246 ms 340 KB Output is correct
15 Correct 250 ms 340 KB Output is correct
16 Correct 246 ms 340 KB Output is correct
17 Correct 244 ms 340 KB Output is correct
18 Correct 249 ms 320 KB Output is correct
19 Correct 279 ms 340 KB Output is correct
20 Correct 244 ms 324 KB Output is correct
21 Correct 756 ms 344 KB Output is correct
22 Correct 773 ms 340 KB Output is correct
23 Correct 753 ms 340 KB Output is correct
24 Correct 794 ms 344 KB Output is correct
25 Incorrect 807 ms 340 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 795 ms 340 KB Output is correct
2 Correct 831 ms 344 KB Output is correct
3 Correct 794 ms 340 KB Output is correct
4 Correct 828 ms 340 KB Output is correct
5 Correct 855 ms 340 KB Output is correct
6 Correct 823 ms 344 KB Output is correct
7 Correct 821 ms 340 KB Output is correct
8 Correct 781 ms 344 KB Output is correct
9 Correct 774 ms 340 KB Output is correct
10 Correct 810 ms 344 KB Output is correct
11 Correct 247 ms 340 KB Output is correct
12 Correct 242 ms 212 KB Output is correct
13 Correct 247 ms 340 KB Output is correct
14 Correct 246 ms 340 KB Output is correct
15 Correct 250 ms 340 KB Output is correct
16 Correct 246 ms 340 KB Output is correct
17 Correct 244 ms 340 KB Output is correct
18 Correct 249 ms 320 KB Output is correct
19 Correct 279 ms 340 KB Output is correct
20 Correct 244 ms 324 KB Output is correct
21 Correct 756 ms 344 KB Output is correct
22 Correct 773 ms 340 KB Output is correct
23 Correct 753 ms 340 KB Output is correct
24 Correct 794 ms 344 KB Output is correct
25 Incorrect 807 ms 340 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 757 ms 340 KB Output is correct
2 Correct 787 ms 344 KB Output is correct
3 Correct 764 ms 344 KB Output is correct
4 Correct 760 ms 340 KB Output is correct
5 Correct 738 ms 364 KB Output is correct
6 Correct 730 ms 352 KB Output is correct
7 Correct 771 ms 344 KB Output is correct
8 Correct 742 ms 348 KB Output is correct
9 Correct 734 ms 348 KB Output is correct
10 Correct 772 ms 344 KB Output is correct
11 Correct 242 ms 340 KB Output is correct
12 Correct 266 ms 340 KB Output is correct
13 Correct 246 ms 340 KB Output is correct
14 Correct 247 ms 348 KB Output is correct
15 Incorrect 245 ms 340 KB Output isn't correct
16 Halted 0 ms 0 KB -