oj.uz

Submission #706291

# Submission time Handle Problem Language Result Execution time Memory
706291 2023-03-06T09:01:42 Z bebra Bulldozer (JOI17_bulldozer) C++17
0 / 100
 59 ms 320 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;
    }
};


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 = 0; 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 = points[i].cost + points[j].cost;
                ll min_pref = min(0LL, pref);
                for (const auto& p : a[t]) {
                    pref += p.cost;
                    min_pref = min(min_pref, pref);
                    ans = max(ans, pref - min_pref);
                }
            }

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

    return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 312 KB Output is correct
2 Correct 51 ms 312 KB Output is correct
3 Correct 51 ms 316 KB Output is correct
4 Correct 59 ms 312 KB Output is correct
5 Correct 56 ms 212 KB Output is correct
6 Correct 53 ms 212 KB Output is correct
7 Correct 50 ms 312 KB Output is correct
8 Correct 53 ms 320 KB Output is correct
9 Correct 52 ms 212 KB Output is correct
10 Correct 56 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Incorrect 1 ms 212 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 312 KB Output is correct
2 Correct 51 ms 312 KB Output is correct
3 Correct 51 ms 316 KB Output is correct
4 Correct 59 ms 312 KB Output is correct
5 Correct 56 ms 212 KB Output is correct
6 Correct 53 ms 212 KB Output is correct
7 Correct 50 ms 312 KB Output is correct
8 Correct 53 ms 320 KB Output is correct
9 Correct 52 ms 212 KB Output is correct
10 Correct 56 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Incorrect 1 ms 212 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 312 KB Output is correct
2 Correct 51 ms 312 KB Output is correct
3 Correct 51 ms 316 KB Output is correct
4 Correct 59 ms 312 KB Output is correct
5 Correct 56 ms 212 KB Output is correct
6 Correct 53 ms 212 KB Output is correct
7 Correct 50 ms 312 KB Output is correct
8 Correct 53 ms 320 KB Output is correct
9 Correct 52 ms 212 KB Output is correct
10 Correct 56 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Incorrect 1 ms 212 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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