Submission #1118193

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118193		bruh	Bulldozer (JOI17_bulldozer)	C++14	5 / 100	87 ms	336 KiB

bulldozer

#include<bits/stdc++.h>
#define int long long
#define ld long double
#define ii array<int, 3>

using namespace std;
const int maxn = 2005;
int n, ans = 0;
array<int, 3> a[maxn], b[maxn];

template <typename T>
struct Point {
    T x;
    T y;
};

Point<ld> X, Y;

template <typename T>
T distance_point_to_line(const Point<T>& P, const Point<T>& A, const Point<T>& B) {
    T dx = B.x - A.x;
    T dy = B.y - A.y;
    T numerator = (dy * (P.x - A.x) - dx * (P.y - A.y));
    T denominator = sqrt(dx * dx + dy * dy);
    return numerator / denominator;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//    freopen("TRUFFLE.inp", "r", stdin);
//    freopen("TRUFFLE.out", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i][0] >> a[i][1] >> a[i][2],
        b[i] = a[i];
    sort(a + 1, a + n + 1);
    sort(b + 1, b + n + 1);
    for (int k = 1, cur = 0; k <= n; k++)
            {
                cur = max(cur, 0ll) + b[k][2];
                ans = max(ans, cur);
            }
    int pre = ans;
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++)
        {
            X.x = a[i][0];
            X.y = a[i][1];
            Y.x = a[j][0];
            Y.y = a[j][1];
            sort(b + 1, b + n + 1, [](ii a, ii b){
                    Point<ld> Z;
                    Z.x = a[0];
                    Z.y = a[1];
                    Point<ld> T;
                    T.x = b[0];
                    T.y = b[1];
                    return distance_point_to_line<ld>(Z, X, Y) < distance_point_to_line<ld>(T, X, Y);
                });

        }
    assert(ans == pre);
    cout << ans;
}

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