提出 #48085642

---

ソースコード 拡げる

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

const int64_t INF = 1E12;

template <class T> int sgn(T x) { return (x > 0) - (x < 0); }
template<class T>
struct Point {
	typedef Point P;
	T x, y;
	explicit Point(T x=0, T y=0) : x(x), y(y) {}
	bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); }
	bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); }
	P operator+(P p) const { return P(x+p.x, y+p.y); }
	P operator-(P p) const { return P(x-p.x, y-p.y); }
	P operator*(T d) const { return P(x*d, y*d); }
	P operator/(T d) const { return P(x/d, y/d); }
	T dot(P p) const { return x*p.x + y*p.y; }
	T cross(P p) const { return x*p.y - y*p.x; }
	T cross(P a, P b) const { return (a-*this).cross(b-*this); }
	T dist2() const { return x*x + y*y; }
	double dist() const { return sqrt((double)dist2()); }
	// angle to x-axis in interval [-pi, pi]
	double angle() const { return atan2(y, x); }
	P unit() const { return *this/dist(); } // makes dist()=1
	P perp() const { return P(-y, x); } // rotates +90 degrees
	P normal() const { return perp().unit(); }
	// returns point rotated 'a' radians ccw around the origin
	P rotate(double a) const {
		return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); }
	friend ostream& operator<<(ostream& os, P p) {
		return os << "(" << p.x << "," << p.y << ")"; }
};

using P = Point<int64_t>;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    vector<array<int, 3>> pts(n + 1);
    pts[0][1] = 1E9 + 7;
    for (int i = 1; i <= n; i++) {
        cin >> pts[i][0] >> pts[i][1] >> pts[i][2];
    }
    sort(pts.begin(), pts.end());
    vector cost(n + 1, vector<int64_t>(n + 1));
    for (int i = 0; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (pts[i][0] == pts[j][0] || pts[i][1] <= pts[j][1]) {
                continue;
            }
            auto [x1, y1, _1] = pts[i];
            auto [x2, y2, _2] = pts[j];
            if (x1 == 0) {
                y1 = y2;
            }
            for (int k = 1; k <= n; k++) {
                auto [x3, y3, w3] = pts[k];
                if (x3 > x1 && x3 <= x2 && P(x1, y1).cross(P(x2, y2), P(x3, y3)) <= 0) {
                    cost[i][j] += w3;
                }
            }
        }
    }
    int64_t ans = 0;
    vector dp(n + 1, vector<int64_t>(n + 1, -INF));
    for (int i = 0; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (pts[i][1] == pts[j][1]) {
                continue;
            }
            if (i == 0) {
                dp[i][j] = cost[i][j];
            } else {
                for (int k = 0; k < i; k++) {
                    if (pts[k][0] == pts[i][0] || pts[k][1] <= pts[i][1]) {
                        continue;
                    }
                    if (k != 0 && P(pts[k][0], pts[k][1]).cross(P(pts[i][0], pts[i][1]), P(pts[j][0], pts[j][1])) >= 0) {
                        // cerr << k << " " << i << " " << j << '\n';
                        continue;
                    }
                    dp[i][j] = max(dp[i][j], dp[k][i] + cost[i][j]);
                }
            }
            ans = max(ans, dp[i][j]);
        }
    }
    cout << ans;
}

提出情報

ジャッジ結果