QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#682811#9529. Farm ManagementChiTangWA 1ms5716kbC++142.3kb2024-10-27 17:25:322024-10-27 17:25:32

Judging History

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

  • [2024-10-27 17:25:32]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5716kb
  • [2024-10-27 17:25:32]
  • 提交

answer

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

#define int long long

const int N = 2e5 + 10;

struct node
{
	int w, l, r;
};
node a[N];
bool cmp(node x, node y)
{
	return x.w > y.w;
}
int pre[N];
int val[N];
int ti;
int flag = 0;
bool check(int x)
{
	if (flag <= x)
	{
		if (ti >= pre[x]-(a[flag].r-a[flag].l))
		{
			return 1;
		}
		else
		{
			return 0;
		}
	}
	else
	{
		if (ti >= pre[x])
		{
			return 1;
		}
		else
		{
			return 0;
		}
	}
}
int bsearch_2(int l, int r)
{
	while (l < r)
	{
		int mid = l + r + 1 >> 1; // 若l = mid,则需要+1
		if (check(mid))
			l = mid;
		else
			r = mid - 1;
	}
	return l;
}

void solve()
{
	int n, m;
	cin >> n >> m;
	int summax = 0;
	int summin = 0;
	int sumval = 0;
	int ans = 0, t = 0;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i].w >> a[i].l >> a[i].r;
		summax+=a[i].r;
		summin+=a[i].l;
		sumval += a[i].r*a[i].w;
	}
	sort(a + 1, a + n + 1, cmp);

	for (int i = 1; i <= n; i++)
	{
		ans += a[i].w * a[i].l;
		t += a[i].l;
	}

	for (int i = 1; i <= n; i++)
	{
		pre[i] = pre[i - 1] + (a[i].r - a[i].l);
		val[i] = val[i - 1] + (a[i].r - a[i].l) * a[i].w;
	}
	// for (int i = 1; i <= n; i++)
	// {
	// 	cout << pre[i] << " ";
	// }
	// cout << endl;
	// for (int i = 1; i <= n; i++)
	// {
	// 	cout << val[i] << " ";
	// }
	// cout << endl;
	int preans = ans;
	// cout<<ans<<endl;
	for (int i = 1; i <= n; i++)
	{
		int tt = t - a[i].l;
		int res = preans - a[i].w * a[i].l;
		ti = m - tt;
		ans = max(ans, res + (ti * a[i].w));
		//cout << ans << endl;
		int l = 1, r = n;
		flag = i;
		int sumi = summax - a[i].r;
		if(sumi-(summin-a[i].l)<ti){
			res = sumval - a[i].r*a[i].w;
			int mu = ti - (sumi-(summin-a[i].l));
			res += mu*a[i].w;
			ans = max(ans,res);
			continue;
		}
		int lp = bsearch_2(l, r);
		//cout << lp << " "<<i<<endl;
		int lef ;//= ti - pre[lp];
		if(lp>=i){
			res += val[lp]-(val[i]-val[i-1]);
			lef= ti -(pre[lp]-(pre[i]-pre[i-1]));
		}else{
			res += val[lp];
			lef = ti-pre[lp];
		}
		
		
		if (lef > 0)
		{
			res += a[lp + 1].w * lef;
		}
		ans = max(ans, res);
		//cout << ans << endl;
	}
	cout << ans << endl;
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	int t = 1;
	//	cin >> t;
	while (t--)
	{
		solve();
	}

	return 0;
}

详细

Test #1:

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

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: 5716kb

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:

36099279

result:

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