QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#678600 | #9529. Farm Management | ucup-team5226# | WA | 0ms | 3760kb | C++20 | 2.4kb | 2024-10-26 15:28:44 | 2024-10-26 15:28:44 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (ll i = 0; i < n; ++i)
void solve() {
ll n, m;
cin >> n >> m;
vector<tuple<ll, ll, ll>> v;
rep(i, n) {
ll w, l, r;
cin >> w >> l >> r;
v.emplace_back(w, l, r);
}
sort(v.begin(), v.end());
ll res = 0, rem = m;
for (auto [w, l, r] : v) {
rem -= l;
res += w * l;
}
vector<pair<ll, ll>> p(n);
rep(i, n) p[i].first = get<1>(v[i]);
for (int i = n - 1; i >= 0; i--) {
auto [w, l, r] = v[i];
ll d = min(rem, r - l);
res += w * d;
rem -= d;
p[i].second = p[i].first + d;
}
vector<ll> suml0, suml1, sumr0, sumr1;
rep(i, n) {
auto [w, l, r] = v[i];
ll d = p[i].first - l;
if (i == 0)
suml0.push_back(d), suml1.push_back(w * d);
else
suml0.push_back(suml0.back() + d), suml1.push_back(suml1.back() + w * d);
}
for (int i = n - 1; i >= 0; i--) {
auto [w, l, r] = v[i];
ll d = r - p[i].second;
if (i == n - 1)
sumr0.push_back(d), sumr1.push_back(w * d);
else
sumr0.push_back(sumr0.back() + d), sumr1.push_back(sumr1.back() + w * d);
}
ll base = res;
rep(i, n) {
auto [w, l, r] = v[i];
{
ll idx = lower_bound(sumr0.begin(), sumr0.end(), p[i].first) - sumr0.begin();
idx = min(idx, n - 1 - i - 1);
ll val = 0, rem = p[i].first;
if (idx) val += sumr1[idx - 1], rem -= sumr0[idx - 1];
val += min(rem, sumr0[idx]) * get<0>(v[n - 1 - idx]);
rem -= min(rem, sumr0[idx]);
val -= (p[i].first - rem) * w;
res = max(res, base + val);
}
{
ll idx = lower_bound(suml0.begin(), suml0.end(), m - p[i].second) - suml0.begin();
idx = min(idx, r - 1);
ll val = 0, rem = m - p[i].second;
if (idx) val -= suml1[idx] - 1, rem -= suml0[idx - 1];
val -= min(rem, suml0[idx]) * get<0>(v[idx]);
rem -= min(rem, suml0[idx]);
val += (m - p[i].second - rem) * w;
res = max(res, val);
}
}
cout << res << endl;
}
int main() {
int t = 1;
// cin >> t;
for (int i = 1; i <= t; i++) solve();
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3760kb
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: 3464kb
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: 3716kb
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:
17015002
result:
wrong answer 1st lines differ - expected: '22000255', found: '17015002'