QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#785106 | #9529. Farm Management | RFIY | WA | 1ms | 5672kb | C++20 | 1.6kb | 2024-11-26 16:52:43 | 2024-11-26 16:52:43 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int N = 2e5 + 10;
struct pp{
ll w, l, r;
}p[N];
ll sum[N], val[N];
bool cmp(pp a, pp b){
return a.w < b.w;
}
void solve(){
ll n, m;
cin >> n >> m;
ll ans = 0, res = 0;
for(int i = 1; i <= n; i ++){
cin >> p[i].w >> p[i].l >> p[i].r;
ans += p[i].w * p[i].l;
res += p[i].l;
}
sort(p + 1, p + n + 1, cmp);
//for(int i = 1; i <= n; i ++) cout << p[i].w << ' ' << p[i].l << ' ' << p[i].r << '\n';
//cout << '\n';
for(int i = n; i >= 1; i --){
sum[i] = sum[i + 1] + p[i].r - p[i].l;
val[i] = val[i + 1] + (p[i].r - p[i].l) * p[i].w;
}
ll ans1 = ans + (m - res) * p[n].w;
for(int i = 1; i <= n; i ++){
ll ti = m - res + p[i].l, cur = ans - p[i].w * p[i].l;
ll l = 0, r = n + 1;
//cout << cur << ' ';
while(r - l > 1){
ll mid = (l + r) / 2;
ll k = sum[mid] + (i >= mid ? (p[i].r - p[i].l) : 0);
if(k > ti) l = mid;
else r = mid;
}
cur += val[r] + min(ti - sum[r], p[l].r - p[l].l) * p[l].w - (i >= r ? p[i].r * p[i].w : 0);
if(ti - sum[l] > 0) cur += (ti - sum[l]) * p[i].w;
//cout << r << ' ' << val[r] << ' ' << sum[r] << ' ' << cur << '\n';
ans1 = max(ans1, cur);
}
cout << ans1 << '\n';
}
int main(){
ios::sync_with_stdio(0), cin.tie(0);
ll 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: 5624kb
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: 0
Accepted
time: 0ms
memory: 5632kb
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:
35204500
result:
ok single line: '35204500'
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 5672kb
input:
15 32 835418 2 3 178262 1 3 527643 2 2 519710 1 1 774544 3 3 82312 1 1 808199 1 1 809396 1 3 255882 1 3 80467 1 3 874973 1 3 813965 1 2 198275 1 2 152356 1 3 802055 1 1
output:
24921376
result:
wrong answer 1st lines differ - expected: '22000255', found: '24921376'