提出 #35890265

---

ソースコード 拡げる

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
typedef long long ll;
using namespace std;
const int maxn = 2005;
const int inf = 1e9;
int gcd(int x, int y) {
	return y ? gcd(y, x % y) : x;
}
int n, L;
struct node {
	int w, x, v;
} a[maxn];
struct frac {
	int x, y;
	frac(int a, int b) {
		x = a, y = b;
		int d = gcd(a, b);
		x /= d, y /= d;
	}
	friend bool operator < (const frac &a, const frac &b) {
		return a.x * b.y < b.x * a.y;
	}
	friend bool operator == (const frac &a, const frac &b) {
		return a.x * b.y == b.x * a.y;
	}
};
struct opt {
	frac x;
	int w;
	opt(frac x = frac(0, 1), int w = 0) : x(x), w(w) {}
} b[maxn * 2];
bool cmp(const node &x, const node &y) {
	return x.x < y.x;
}
int main() {
#ifdef DEBUG
	freopen("1.in", "r", stdin);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> L;
	for(int i = 1; i <= n; i++) {
		cin >> a[i].w >> a[i].x >> a[i].v;
	}
	sort(a + 1, a + 1 + n, cmp);
	int ans = 0;
	for(int i = 1; i <= n; i++) {
		int cnt = 0;
		int sum = a[i].w;
		for(int j = 1; j < i; j++) {
			if(a[j].v < a[i].v) {
				if(a[i].x == a[j].x) {
					b[++cnt] = opt(frac(0, 1), a[j].w);
					b[++cnt] = opt(frac(0, 1), -a[j].w);
				}
				continue;
			}
			if(a[j].v == a[i].v) {
				if(a[i].x == a[j].x) {
					sum += a[j].w;
				}
				continue;
			}
			b[++cnt] = opt(frac(a[i].x - a[j].x, a[j].v - a[i].v), a[j].w);
			b[++cnt] = opt(frac(a[i].x + L - a[j].x, a[j].v - a[i].v), -a[j].w);
		}
		for(int j = i + 1; j <= n; j++) {
			if(a[j].v == a[i].v) {
				if(a[i].x + L >= a[j].x) {
					sum += a[j].w;
				}
				continue;
			}
			if(a[j].v > a[i].v) {
				if(a[j].x <= a[i].x + L) {
					b[++cnt] = opt(frac(0, 1), a[j].w);
					b[++cnt] = opt(frac(a[i].x + L - a[j].x, a[j].v - a[i].v), -a[j].w);
				}
				continue;
			}
			frac l = frac(0, 1);
			if(a[j].x > a[i].x + L) {
				l = frac(a[j].x - a[i].x - L, a[i].v - a[j].v);
			}
			b[++cnt] = opt(l, a[j].w);
			b[++cnt] = opt(frac(a[j].x - a[i].x, a[i].v - a[j].v), -a[j].w);
		}
		sort(b + 1, b + 1 + cnt, [&](opt x, opt y) {
			if(x.x == y.x) {
				return x.w > y.w;
			}
			else {
				return x.x < y.x;
			}
		});
//		cout << sum << '\n';
//		for(int j = 1; j <= cnt; j++) {
//			cout << b[j].x << ' ' << b[j].w << ' ' << b[j].o << '\n';
//		}
		ans = max(ans, sum);
		for(int j = 1; j <= cnt; ) {
			int k = j;
			while(k <= cnt && b[k].x == b[j].x && (b[k].w >= 0) == (b[j].w >= 0)) {
				sum += b[k].w;
				k++;
			}
//			cout << sum << ' ';
			ans = max(ans, sum);
			j = k;
		}
//		cout << '\n';
//		cout << '\n';
	}
	cout << ans << '\n';
	return 0;
}

提出情報

ジャッジ結果