QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#679475 | #9529. Farm Management | ucup-team3670# | WA | 0ms | 3792kb | C++17 | 1.6kb | 2024-10-26 17:41:24 | 2024-10-26 17:41:24 |
Judging History
answer
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define fore(i, l, r) for (int i = int(l); i < int(r); ++i)
using namespace std;
int main(){
cin.tie(0);
ios::sync_with_stdio(false);
int n;
long long m;
cin >> n >> m;
vector<int> w(n), l(n), r(n);
forn(i, n){
cin >> w[i] >> l[i] >> r[i];
}
long long ans = 0;
long long sl = 0;
forn(i, n) sl += l[i];
long long sl2 = 0;
forn(i, n) sl2 += l[i] * 1ll * w[i];
vector<long long> su(n + 1), su2(n + 1);
for (int i = n - 1; i >= 0; --i){
su[i] = su[i + 1] + (r[i] - l[i]);
su2[i] = su2[i + 1] + (r[i] - l[i]) * 1ll * w[i];
}
forn(i, n){
long long lft = m - sl + l[i];
ans = max(ans, sl2 - l[i] * 1ll * w[i] + lft * 1ll * w[i]);
}
forn(i, n){
int lf = 0, rg = n - 1;
int res = -1;
while (lf <= rg){
int mid = (lf + rg) / 2;
long long mx = su[mid] - (i <= mid ? r[i] - l[i] : 0);
mx += sl - l[i];
if (mx >= m){
res = mid;
rg = mid - 1;
}
else{
lf = mid + 1;
}
}
if (res == 0 && i == 0) res = -1;
assert(res != i);
if (res == -1){
long long rem = m - (sl + su[0] - r[i]);
ans = max(ans, (sl2 + su2[0] - r[i] * 1ll * w[i]) + rem * w[i]);
}
else{
long long cur = su2[res] - (i <= res ? (r[i] - l[i]) * 1ll * w[i] : 0ll);
cur += sl2 - l[i] * 1ll * w[i];
long long rem = su[res] - (i <= res ? r[i] - l[i] : 0);
rem += sl - l[i];
assert(rem >= m);
rem -= m;
ans = max(ans, cur - w[res] * 1ll * rem);
}
}
cout << ans << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3748kb
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: 3792kb
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:
33655073
result:
wrong answer 1st lines differ - expected: '35204500', found: '33655073'