Submission #1117782

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117782		Pannda	Bulldozer (JOI17_bulldozer)	C++17	25 / 100	2051 ms	35488 KiB

bulldozer

#include <bits/stdc++.h>
using namespace std;

typedef long double F;
typedef complex<F> point;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<point> a(n);
    vector<int> w(n);
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y >> w[i];
        a[i] = point(x, y);
    }

    vector<F> thetas = [&] { // Gives a list of critical points in [-pi/2,pi/2) in order, expressed by (i, j) : before the critical point i<j and after that i>j. When exactly are the critical points are not returned
        vector<F> res = {-1.57079632679};
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (y0 != y1) {
                    F tan = (a[i].real() - a[j].real()) / (a[i].imag() - a[j].imag());
                    res.push_back(atan(tan));
                }
            }
        }
        sort(res.begin(), res.end());
        return res;
    }();

    long long ans = 0;
    for (F theta : thetas) {
        vector<int> p(n);
        iota(p.begin(), p.end(), 0);
        sort(p.begin(), p.end(), [&](int i, int j) -> bool {
            point x(cos(theta) * a[i].real() - sin(theta) * a[i].imag(), sin(theta) * a[i].real() + cos(theta) * a[i].imag());
            point y(cos(theta) * a[j].real() - sin(theta) * a[j].imag(), sin(theta) * a[j].real() + cos(theta) * a[j].imag());
            return x.real() < y.real();
        });
        long long sum = 0;
        long long mnsum = 0;
        for (int i : p) {
            sum += w[i];
            ans = max(ans, sum - mnsum);
            mnsum = min(mnsum, sum);
        }
    }

    cout << ans << '\n';

}

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