QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#725431#9529. Farm ManagementSTASISZHYWA 2ms9836kbC++141.4kb2024-11-08 17:44:262024-11-08 17:44:28

Judging History

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

  • [2024-11-08 17:44:28]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:9836kb
  • [2024-11-08 17:44:26]
  • 提交

answer

// Problem: B - Farm Management
// Contest: Virtual Judge - 思维
// URL: https://vjudge.net/contest/670080#problem/B
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define PII pair<int, int>

using namespace std;

const int N = 2e5 + 10, M = 1e6 + 10, mod = 1e9 + 7, INF = 0x3f3f3f3f;

int n, m, q, ans;
int dp[N], sum1[N], sum2[N], res1[N], res2[N];

vector<int> e[N];

struct node
{
	int v, l, r;
}s[N];

inline bool cmp(node a, node b) {return a.v > b.v;}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i ++) cin >> s[i].v >> s[i].l >> s[i].r;
	sort(s + 1, s + n + 1, cmp);
	for(int i = 1; i <= n; i ++)
	{
		sum1[i] = sum1[i - 1] + s[i].l, sum2[i] = sum2[i - 1] + (s[i].r - s[i].l);
		res1[i] = res1[i - 1] + s[i].v * s[i].l, res2[i] = res2[i - 1] + s[i].v * (s[i].r - s[i].l);
	}
	for(int i = 1; i <= n; i ++)
	{
		int now = m - (sum1[n] - s[i].l), res = res1[n] - s[i].l * s[i].v;
		if(now < 0) continue;
		else
		{
			if(now > sum2[i - 1]) res += res2[i - 1] + (now - sum2[i - 1]) * s[i].v;
			else
			{
				int id = upper_bound(sum2, sum2 + i - 1, now) - sum2 - 1;
				res += res2[id] + (now - sum2[id]) * s[i].v;
			}
		}
		ans = max(ans, res);
	}
	cout << ans << '\n';
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 9836kb

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

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:

34859047

result:

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