QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#743017 | #9529. Farm Management | guanghere | WA | 1ms | 5612kb | C++23 | 2.4kb | 2024-11-13 17:56:41 | 2024-11-13 17:56:42 |
Judging History
answer
//
// Created by 24087 on 24-11-13.
//
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1e5 + 5;
long long n, m, ans, sigma_l, now_val,srw,sr, sum_len_to_fill[N], sum_val_to_fill[N],
left_time;
struct Crop {
long long w = 0, l = 0, r = 0;
} crop[N];
bool operator<(const Crop &a, const Crop &b) { return a.w > b.w; }
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> crop[i].w >> crop[i].l >> crop[i].r;
sigma_l += crop[i].l;
now_val += crop[i].l * crop[i].w;
srw += crop[i].r * crop[i].w;
sr+=crop[i].r;
}
sort(crop + 1, crop + n + 1);
ans = now_val + (m - sigma_l) * crop[1].w;
left_time = m - sigma_l;
int first_unimplemented = 0;
for (int i = 1; i <= n && left_time; first_unimplemented = ++i) {
const long long delta = min(left_time, crop[i].r - crop[i].l);
//std::cerr << "i = " << i << " delta = " << delta << '\n';
left_time -= delta;
now_val += delta * crop[i].w;
crop[i].l += delta;
}
for (int i = first_unimplemented; i <= n; i++) {
sum_len_to_fill[i] = sum_len_to_fill[i - 1] + crop[i].r - crop[i].l;
sum_val_to_fill[i] =
sum_val_to_fill[i - 1] + crop[i].w * (crop[i].r - crop[i].l);
//std::cerr << "i = " << i << " sum_len_to_fill = " << sum_len_to_fill[i] << " sum_val_to_fill = " << sum_val_to_fill[i] << '\n';
}
//sum_val_to_fill[]
//std::cerr << "first_unimplemented = " << first_unimplemented << '\n';
for (int i = first_unimplemented + 1; i <= n; i++) {
int idx =
static_cast<int>(lower_bound(sum_len_to_fill + first_unimplemented,
sum_len_to_fill + 1 + n, crop[i].l) -
sum_len_to_fill);
long long tmp_ans = now_val;
if(idx == n + 1) {
tmp_ans=srw+crop[i].w*(m-sr);
ans = max(ans, tmp_ans);
// cerr<<tmp_ans<<endl;
continue;
}
tmp_ans -= (crop[i].l - sum_len_to_fill[idx - 1]) * crop[i].w;
tmp_ans += sum_val_to_fill[idx - 1] + crop[idx].w * (crop[i].l - sum_len_to_fill[idx - 1]);
ans = max(ans, tmp_ans);
std::cerr << "i = " << i << " idx = " << idx << " tmp_ans = " << tmp_ans << '\n';
}
std::cout << ans << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5600kb
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: 5612kb
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:
36636800
result:
wrong answer 1st lines differ - expected: '35204500', found: '36636800'