QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#693064 | #9529. Farm Management | ucup-team3519# | WA | 0ms | 3612kb | C++17 | 2.0kb | 2024-10-31 15:28:10 | 2024-10-31 15:28:15 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
#define fi first
#define se second
#define V vector
#define pb push_back
typedef long long LL;
void solve() {
LL base_use = 0, base_money = 0;
LL n, m; cin >> n >> m;
V<LL> l(n + 1), r(n + 1), w(n + 1);
V<int> ord(n + 1);
iota(ord.begin() + 1, ord.end(), 1);
sort(ord.begin() + 1, ord.end(), [&](int x, int y) {
return w[x] < w[y];
});
auto modify = [&](V<LL> &x) -> void {
V<LL> tmp(n + 1);
for(int i = 1; i <= n; i++) tmp[i] = x[ord[i]];
swap(tmp, x);
};
modify(l);
modify(r);
modify(w);
for(int i = 2; i <= n; i++) assert(w[i] >= w[i - 1]);
for(int i = 1; i <= n; i++) {
cin >> w[i] >> l[i] >> r[i];
}
for(int i = 1; i <= n; i++) {
base_use += l[i];
base_money += l[i] * w[i];
}
V<LL> extra_use_suffix(n + 1);
for(int i = n; i >= 1; i--) {
extra_use_suffix[i] = r[i] - l[i];
if(i != n) extra_use_suffix[i] += extra_use_suffix[i + 1];
}
V<LL> extra_money_suffix(n + 1);
for(int i = n; i >= 1; i--) {
extra_money_suffix[i] = (r[i] - l[i]) * w[i];
if(i != n) extra_money_suffix[i] += extra_money_suffix[i + 1];
}
LL ans = 0;
for(int i = 1; i <= n; i++) {
LL res = m - base_use + l[i];
LL cur = base_money - l[i] * w[i];
int L = i, R = n + 1;
while(L != R - 1) {
int mid = L + R >> 1;
if(extra_use_suffix[mid] <= res) {
R = mid;
} else L = mid;
}
if(R <= n) {
res -= extra_use_suffix[R];
cur += extra_money_suffix[R];
}
//R - 1 ...
cur += res * w[R - 1];
ans = max(cur, ans);
//upd
}
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
// int t; cin >> t;
// while(t--)
solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3612kb
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: 3548kb
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:
34616000
result:
wrong answer 1st lines differ - expected: '35204500', found: '34616000'