QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#684173 | #9529. Farm Management | WanShi | WA | 0ms | 3716kb | C++14 | 1.7kb | 2024-10-28 11:05:34 | 2024-10-28 11:05:34 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const int N = 2e5 + 5;
int __ = 1, n = 0, m;
string s;
int valr[N], vall[N], vr[N];
struct ifo
{
int l, r, w;
bool operator<(const ifo &a) const
{
return w > a.w;
}
} info[N];
int sumr = 0, suml = 0;
void solve()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> info[i].w >> info[i].l >> info[i].r;
sumr += info[i].r;
suml += info[i].l;
}
info[0] = {0, 0, 0};
sort(info + 1, info + n + 1);
int ans = 0;
for (int i = 1; i <= n; i++)
{
ans += info[i].l * info[i].w;
valr[i] = valr[i - 1] + info[i].r * info[i].w;
vall[i] = vall[i - 1] + info[i].l * info[i].w;
vr[i] = vr[i - 1] + info[i].r - info[i].l;
}
ans += (m - suml) * info[1].w;
for (int i = 1; i <= n; i++)
{
if (sumr - info[i].r <= m)
{
ans = max(ans, (valr[i] - info[i].r * info[i].w) - info[i].w * (m - (sumr - info[i].r)));
continue;
}
int l = 0, r = i - 1;
while (l < r)
{
int mid = (l + r + 1) / 2;
if (vr[mid] <= info[i].l)
l = mid;
else
r = mid - 1;
}
int tans = 0;
if (l + 1 < i)
tans += (info[i].l - vr[l]) * info[l + 1].w;
tans += valr[l] + (vall[n] - vall[l] - info[i].l * info[i].w);
ans = max(ans, tans);
}
cout << ans << endl;
return;
}
int32_t main()
{
#ifdef ONLINE_JUDGE
ios::sync_with_stdio(false);
cin.tie(0);
#endif
// cin >> __;
while (__--)
solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3628kb
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: 3716kb
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:
34309721
result:
wrong answer 1st lines differ - expected: '35204500', found: '34309721'