oj.uz

Submission #706312

# Submission time Handle Problem Language Result Execution time Memory
706312 2023-03-06T09:21:09 Z bebra Bulldozer (JOI17_bulldozer) C++17
0 / 100
 2000 ms 356 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 <= 300; ++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 1924 ms 356 KB Output is correct
2 Correct 1893 ms 352 KB Output is correct
3 Correct 1921 ms 352 KB Output is correct
4 Correct 1922 ms 356 KB Output is correct
5 Correct 1946 ms 356 KB Output is correct
6 Correct 1916 ms 352 KB Output is correct
7 Correct 1957 ms 356 KB Output is correct
8 Correct 1954 ms 356 KB Output is correct
9 Correct 1920 ms 352 KB Output is correct
10 Correct 1915 ms 348 KB Output is correct
11 Correct 821 ms 348 KB Output is correct
12 Correct 835 ms 356 KB Output is correct
13 Correct 841 ms 340 KB Output is correct
14 Correct 843 ms 348 KB Output is correct
15 Incorrect 868 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 1941 ms 356 KB Output is correct
2 Execution timed out 2033 ms 356 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1941 ms 356 KB Output is correct
2 Execution timed out 2033 ms 356 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1941 ms 356 KB Output is correct
2 Execution timed out 2033 ms 356 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1924 ms 356 KB Output is correct
2 Correct 1893 ms 352 KB Output is correct
3 Correct 1921 ms 352 KB Output is correct
4 Correct 1922 ms 356 KB Output is correct
5 Correct 1946 ms 356 KB Output is correct
6 Correct 1916 ms 352 KB Output is correct
7 Correct 1957 ms 356 KB Output is correct
8 Correct 1954 ms 356 KB Output is correct
9 Correct 1920 ms 352 KB Output is correct
10 Correct 1915 ms 348 KB Output is correct
11 Correct 821 ms 348 KB Output is correct
12 Correct 835 ms 356 KB Output is correct
13 Correct 841 ms 340 KB Output is correct
14 Correct 843 ms 348 KB Output is correct
15 Incorrect 868 ms 340 KB Output isn't correct
16 Halted 0 ms 0 KB -