QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#684789 | #9529. Farm Management | maburb# | WA | 0ms | 3740kb | C++20 | 1.6kb | 2024-10-28 15:54:00 | 2024-10-28 15:54:04 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
struct Node {
i64 w, l, r;
};
void solve() {
i64 n, m;
std::cin >> n >> m;
std::vector<Node> a(n + 1);
for (int i = 1; i <= n; ++ i) {
i64 w, l, r;
std::cin >> w >> l >> r;
a[i] = {w, l, r};
}
std::sort(a.begin() + 1, a.end(), [&](Node & a, Node & b){
return a.w < b.w;
});
i64 lsum = 0, ltot = 0;
for (int i = 1; i <= n; ++ i) {
auto & [w, l, r] = a[i];
lsum += l;
ltot += w * l;
}
i64 ans = 0;
for (int i = 1; i <= n; ++ i) {
auto & [w, l, r] = a[i];
i64 sum = m - (lsum - l);
i64 tot = ltot - l * w;
ans = std::max(ans, tot + sum * w);
}
std::vector<i64> suf(n + 2), sufw(n + 2);
for (int i = n; i >= 1; -- i) {
suf[i] = suf[i + 1] + a[i].r - a[i].l;
sufw[i] = sufw[i + 1] + (a[i].r - a[i].l) * a[i].w;
}
// auto check = [&](int i, int j) -> i64 {
// if (i > j) {
// return suf[i];
// }
// i64 sum = suf[j + 1] + suf[i] - suf[j];
// return sum;
// };
for (int i = 1; i <= n; ++ i) {
i64 sum = m - (lsum - a[i].l);
i64 tot = ltot - a[i].l * a[i].w;
int l = 1, r = n;
while (l < r) {
int mid = l + r >> 1;
if (suf[mid] <= sum) {
r = mid;
} else {
l = mid + 1;
}
}
// std::cout << l << " " << tot << " ";
tot += sufw[l];
sum -= suf[l];
-- l;
tot += sum * a[l].w;
// std::cout << tot << "\n";
ans = std::max(ans, tot);
}
std::cout << ans << "\n";
}
int main() {
std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
int T = 1;
// std::cin >> T;
while (T -- ) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3740kb
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: 3608kb
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:
35309054
result:
wrong answer 1st lines differ - expected: '35204500', found: '35309054'