QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#685205#9529. Farm Management2317663977WA 1ms5704kbC++232.5kb2024-10-28 18:15:482024-10-28 18:15:48

Judging History

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

  • [2024-10-28 18:15:48]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5704kb
  • [2024-10-28 18:15:48]
  • 提交

answer

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <cmath>
#include <cstring>

using ll = long long;

const int N = 1e5 + 10;

ll n, m;
struct Node
{
	ll l, r, w;
	bool operator<(const Node& t)const
	{
		return w < t.w;
	}
}node[N];
ll lsum[N], rsum[N];
ll bu[N], buzhi[N];
int pos = 1;

bool check(int x, ll zhi)
{
	ll t = bu[pos] - bu[x - 1];
	return t >= zhi;
}

void solve()
{
	cin >> n >> m;
	for (int i = 1;i <= n;i++)
	{
		ll l, r, w;
		cin >> w >> l >> r;
		node[i] = { l,r,w };
	}
	sort(node + 1, node + 1 + n);
	for (int i = 1;i <= n;i++)
	{
		lsum[i] = node[i].l;
		lsum[i] += lsum[i - 1];
		rsum[i] = node[i].r;
		rsum[i] += rsum[i - 1];
	}
	ll ans = 0;
	ll fen = 0;
	for (int i = 1;i <= n;i++)
	{
		ll t = m - (lsum[i - 1] + rsum[n] - rsum[i]);
		//cout << t << ' ' << r[i] - r[i - 1] << ' ' << l[i] - l[i - 1] << '\n';
		if (t <= rsum[i] - rsum[i - 1] && t >= lsum[i] - lsum[i - 1])
		{
			pos = i;
			fen = t;
			break;
		}
	}

	ll yuan = 0;
	for (int i = 1;i <= n;i++)
	{
		if (i < pos) yuan += node[i].l * node[i].w;
		else if (i > pos) yuan += node[i].r * node[i].w;
		else yuan += fen * node[i].w;
	}


	for (int i = 1;i < pos;i++)
	{
		bu[i] = node[i].r - node[i].l;
		buzhi[i] = bu[i] * node[i].w;
		bu[i] += bu[i - 1];
		buzhi[i] += buzhi[i - 1];
	}
	bu[pos] = node[pos].r - fen;
	buzhi[pos] = bu[pos] * node[pos].w;
	bu[pos] += bu[pos - 1];
	buzhi[pos] += buzhi[pos - 1];

	for (int i = 1;i < n;i++)
		ans += node[i].w * node[i].l;
	ans += node[n].w * (m - lsum[n - 1]);
	ans = max(ans, yuan);

	//cout << pos << '\n';

	for (int i = 1;i < pos;i++)
	{
		if (node[i].l >= bu[pos] - bu[i])
		{
			ll res = yuan + (buzhi[pos] - buzhi[i]) - (bu[pos] - bu[i]) * node[i].w;
			//cout << yuan << ' ' << (buzhi[pos] - buzhi[i]) << ' ' << (bu[pos] - bu[i]) << '\n';
			//cout << res << '\n';
			ans = max(ans, res);
			continue;
		}
		int l = i + 1, r = pos;
		ll zhi = node[i].l;
		while (l < r)
		{
			int mid = l + r + 1 >> 1;
			if (check(mid, zhi)) l = mid;
			else r = mid - 1;
		}
		ll res = yuan + (buzhi[pos] - buzhi[l]) + (node[i].l - (bu[pos] - bu[l]) - node[l].l) * node[l].w - node[i].l * node[i].w;
		//cout << l << '\n';
		ans = max(ans, res);
	}
	cout << ans << '\n';
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5704kb

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: 1ms
memory: 5672kb

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:

33388165

result:

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