QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#725431 | #9529. Farm Management | STASISZHY | WA | 2ms | 9836kb | C++14 | 1.4kb | 2024-11-08 17:44:26 | 2024-11-08 17:44:28 |
Judging History
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'