QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#684789#9529. Farm Managementmaburb#WA 0ms3740kbC++201.6kb2024-10-28 15:54:002024-10-28 15:54:04

Judging History

你现在查看的是最新测评结果

  • [2024-10-28 15:54:04]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3740kb
  • [2024-10-28 15:54:00]
  • 提交

answer

#include <bits/stdc++.h>

using i64 = long long;

struct Node {
	i64 w, l, r;
};

void solve() {
	i64 n, m;
	std::cin >> n >> m;
	std::vector<Node> a(n + 1);
	for (int i = 1; i <= n; ++ i) {
		i64 w, l, r;
		std::cin >> w >> l >> r;
		a[i] = {w, l, r};
	}

	std::sort(a.begin() + 1, a.end(), [&](Node & a, Node & b){
		return a.w < b.w;
	});

	i64 lsum = 0, ltot = 0;
	for (int i = 1; i <= n; ++ i) {
		auto & [w, l, r] = a[i];
		lsum += l;
		ltot += w * l;
	}

	i64 ans = 0;
	for (int i = 1; i <= n; ++ i) {
		auto & [w, l, r] = a[i];
		i64 sum = m - (lsum - l);
		i64 tot = ltot - l * w;
		ans = std::max(ans, tot + sum * w);
	}

	std::vector<i64> suf(n + 2), sufw(n + 2);
	for (int i = n; i >= 1; -- i) {
		suf[i] = suf[i + 1] + a[i].r - a[i].l;
		sufw[i] = sufw[i + 1] + (a[i].r - a[i].l) * a[i].w;
	}

	// auto check = [&](int i, int j) -> i64 {
	// 	if (i > j) {
	// 		return suf[i];
	// 	}	

	// 	i64 sum = suf[j + 1] + suf[i] - suf[j];
	// 	return sum;
	// };

	for (int i = 1; i <= n; ++ i) {
		i64 sum = m - (lsum - a[i].l);
		i64 tot = ltot - a[i].l * a[i].w;
		int l = 1, r = n;
		while (l < r) {
			int mid = l + r >> 1;
			if (suf[mid] <= sum) {
				r = mid;
			} else {
				l = mid + 1;
			}
		}

		// std::cout << l << " " << tot  << " ";

		tot += sufw[l];
		sum -= suf[l];
		-- l;
		tot += sum * a[l].w;
		// std::cout << tot << "\n";
		ans = std::max(ans, tot);
	}

	std::cout << ans << "\n";
}

int main() {
	std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
	int T = 1;
	// std::cin >> T;
	while (T -- ) {
		solve();
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3740kb

input:

5 17
2 3 4
6 1 5
8 2 4
4 3 3
7 5 5

output:

109

result:

ok single line: '109'

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3608kb

input:

12 62
503792 9 10
607358 1 3
600501 10 10
33249 4 4
774438 6 6
197692 3 6
495807 8 8
790225 5 9
77272 3 8
494819 4 9
894779 3 9
306279 5 6

output:

35309054

result:

wrong answer 1st lines differ - expected: '35204500', found: '35309054'