QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#701643 | #9529. Farm Management | fosov# | WA | 0ms | 3740kb | C++14 | 1.4kb | 2024-11-02 14:28:31 | 2024-11-02 14:28:32 |
Judging History
answer
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
#define LNF 0x3f3f3f3f3f3f3f3fll
#define MOD 998244353
#define pii pair<int, int>
#define N 100010
ll sz[N], w[N], rem[N], psum[N];
tuple<int, int, int> a[N];
int bsl(int l, int r, ll x) {
while (l < r) {
int m = (l + r) >> 1;
if (sz[m] <= x) {
l = m+1;
} else {
r = m;
}
}
return r - 1;
}
int main() {
#ifdef TEST
freopen("zz.in", "r+", stdin);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll n, m; cin >> n >> m;
ll mm = 0, mw = 0;
for (int i = 1; i <= n; ++ i) {
int w, l, r; cin >> w >> l >> r;
a[i] = make_tuple(w, l, r);
mm += l;
mw += 1ll * l * w;
}
sort(a+1, a+n);
reverse(a+1, a+n);
for (int i = 1; i <= n; ++ i) {
auto& [_w, _l, _r] = a[i];
w[i] = _w;;
rem[i] = _r - _l;
sz[i] = rem[i] + sz[i-1];
psum[i] = rem[i] * w[i] + psum[i-1];
}
ll res = 0;
for (int i = 1; i <= n; ++ i) {
auto& [_w, _l, _r] = a[i];
ll pm = m - (mm - _l);
ll cw = mw - 1ll * _l * _w;
int idx = bsl(0, i, pm);
ll contr = psum[idx] + w[i] * (pm - sz[idx]);
res = max(res, cw + contr);
}
cout << res << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3624kb
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: 3740kb
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:
34859047
result:
wrong answer 1st lines differ - expected: '35204500', found: '34859047'