QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#685205 | #9529. Farm Management | 2317663977 | WA | 1ms | 5704kb | C++23 | 2.5kb | 2024-10-28 18:15:48 | 2024-10-28 18:15:48 |
Judging History
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'