QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#683257 | #9529. Farm Management | HHAZ# | WA | 0ms | 3704kb | C++20 | 2.1kb | 2024-10-27 19:42:57 | 2024-10-27 19:42:59 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
#define endl '\n'
#define sz(x) (int)(x).size()
#define all(t) (t).begin(), (t).end()
#define rep(i, a, b) for (ll i = (a); i <= (b); ++i)
#define per(i, a, b) for(ll i = (a); i >= (b); --i)
#define debug(x) cout<<#x<<": "<<x<<endl
const int N=2e5+10,M=1e6+10;
struct node {
ll l;
ll r;
ll w;
};
bool cmp(node x, node y) {
return x.w < y.w;
}
void solve()
{
int n, m;
cin >> n >> m;
node a[n + 5];
ll sl[n + 5], sr[n + 5], ansl[n + 5], ansr[n + 5];
memset(sl, 0, sizeof(sl));
memset(sr, 0, sizeof(sr));
memset(ansl, 0, sizeof(ansl));
memset(ansr, 0, sizeof(ansr));
rep(i, 1, n) {
cin >> a[i].w >> a[i].l >> a[i].r;
}
sort(a + 1, a + n + 1, cmp);
rep(i, 1, n) {
sl[i] = sl[i - 1] + a[i].l;
sr[i] = sr[i - 1] + a[i].r;
ansl[i] = ansl[i - 1] + a[i].l * a[i].w;
ansr[i] = ansr[i - 1] + a[i].r * a[i].w;
}
ll maxx = 0;
rep(i, 1, n) {
ll x = m - sl[i - 1], ans = ansl[i - 1], l = i + 1, r = n;
if(i == n || a[n].r + sl[n - 1] - sl[i] >= x) {
maxx = max(maxx, ans + ansl[n - 1] - ansl[i] + max(x - sl[n - 1] + sl[i], 0ll) * a[n].w);
}
while(l < r) {
ll mid = (l + r) >> 1;
if(sr[n] - sr[mid - 1] + sl[mid - 1] - sl[i] <= x) {
r = mid;
}
else {
l = mid + 1;
}
}
ans += ansr[n] - ansr[l - 1];
x -= sr[n] - sr[l - 1];
ans += ansl[l - 1] - ansl[i];
x -= sl[l - 1] - sl[i];
ans += x * a[i].w;
maxx = max(maxx, ans);
}
cout << maxx;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1;
// cin >> T;
// cout.flush();
// ofstream outfile("C:\\Users\\86187\\OneDrive\\桌面\\1.txt");
// outfile << "a[1]=0;a[2]=1;";
// ll l = 1e7 + 1;
// rep(i, 3, 1e9) {
// printf("%lld\n", i);
// ll x = (i - 1) * ((a[i - 1] + a[i - 2]) % mod);
// x %= mod;
// if(i == l) {
// outfile << "a[" << i << "]=" << x << ";";
// }
// if(i == l + 1) {
// outfile << "a[" << i << "]=" << x << ";";
// l += 1e7;
// }
// }
while(T--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3704kb
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: 3656kb
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:
36066030
result:
wrong answer 1st lines differ - expected: '35204500', found: '36066030'