如果我 WA on #17,我该怎么办?
查看原帖
如果我 WA on #17,我该怎么办?
546730
billtun楼主2024/8/30 11:14

RT

#include <bits/stdc++.h>
#define eps (1e-9)
#define INF 2147483600
#define Maxn 2005

using namespace std;

int n, tn, len, Maxl = -INF;
double l[Maxn], r[Maxn]; bool fl;
struct Fish {
	int x, v, w;
} tf[Maxn], p[Maxn];
bool Cmp_Fish(Fish a, Fish b) {
	if (a.x == b.x) {
		if (a.v == b.v) { return a.w > b.w; }
		return a.v < b.v;
	} return a.x < b.x;
}

int tot = 0, lw;
struct Node {
	double x; int val;
} ad[Maxn << 1];
bool Cmp_Node(Node a, Node b) {
	return (a.x < b.x);
}

struct BIT {
	int c[Maxn << 1];
	void clear() { memset(c, 0, sizeof c); }
	int lowbit(int x) { return ((x) & (-x)); }
	void add(int x, int val) {
		for (int i = x; i < (n << 1); i += lowbit(i)) {
			c[i] += val;
		}
	} int query(int x) {
		int sum = 0;
		for (int i = x; i; i -= lowbit(i)) {
			sum += c[i];
		} return sum;
	}
} bt;

void Solve(int x) {
	memset(l, 0, sizeof l);
	memset(r, 0, sizeof r);
	
	tot = 0;
	for (int i = 1; i <= n; i ++) {
		fl = 1;
		if (i == x) { // Get L and R
			l[i] = -INF, r[i] = INF;
		} else {
			if (p[i].x > p[x].x) {
				if (p[i].v > p[x].v) {
					if (p[i].x <= p[x].x + len) {
						l[i] = 0.0, r[i] = (p[x].x + len - p[i].x) * 1.0 / (p[i].v - p[x].v);
					} else {
						fl = 0;
					}
				} else if (p[i].v == p[x].v) {
					if (p[i].x <= p[x].x + len) {
						l[i] = -INF, r[i] = INF;
					} else {
						fl = 0;
					}
				} else {
					if (p[i].x <= p[x].x + len) {
						l[i] = 0, r[i] = (p[i].x - p[x].x) * 1.0 / (p[x].v - p[i].v);
					} else{
						l[i] = (p[i].x - p[x].x - len) * 1.0 / (p[x].v - p[i].v);
						r[i] = (p[i].x - p[x].x) * 1.0 / (p[x].v - p[i].v);
					}
				}
			} else if (p[i].x == p[x].x) {
				l[i] = 0;
				if (p[i].v > p[x].v) {
					r[i] = (len * 1.0) * 1.0 / (p[i].v - p[x].v);
				} else {
					r[i] = 0.0;
				}
			} else {
				if (p[i].v > p[x].v) {
					l[i] = (p[x].x - p[i].x) * 1.0 / (p[i].v - p[x].v), r[i] = (p[x].x - p[i].x + len) * 1.0 / (p[i].v - p[x].v);
				} else {
					fl = 0;
				}
			}
		}
		
		if (!fl) { continue; }
		ad[++ tot].x = l[i], ad[tot].val = p[i].w;
		ad[++ tot].x = r[i] + eps, ad[tot].val = -p[i].w;
	} sort(ad + 1, ad + tot + 1, Cmp_Node);
	
	lw = 0;
	for (int i = 1; i <= tot; i ++) {
		if (ad[i].x != ad[i - 1].x) {
			lw ++;
		} bt.add(lw, ad[i].val);
	}
	
	for (int i = 0; i <= lw; i ++) {
		Maxl = max(Maxl, bt.query(i));
	} bt.clear();
}

int main () {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> tn >> len;
	for (int i = 1; i <= tn; i ++) {
		cin >> tf[i].w >> tf[i].x >> tf[i].v;
	} sort(tf + 1, tf + n + 1, Cmp_Fish);
	
	for (int i = 1; i <= tn; i ++) {
		if (tf[i].x != p[n].x || tf[i].v != p[n].v) {
			p[++ n] = tf[i];
		} else { p[n].w += tf[i].w; }
	}
	
	Maxl = 0;
	for (int NowFish = 1; NowFish <= n; NowFish ++) {
		Solve(NowFish);
	} cout << Maxl;
	return 0;
}
/*
5 3
10000 2 9
1 6 1
10 8 2
100 10 1
1000 10 3

11110
*/
2024/8/30 11:14
加载中...