QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#693867 | #9529. Farm Management | wirepuller | WA | 0ms | 3808kb | C++14 | 2.1kb | 2024-10-31 16:52:49 | 2024-10-31 16:52:51 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define mp make_pair
#define endl '\n'
#define dbug() cout << '||||||debug|||||' << endl;
#define fo(i,l,r) for(int i=(l);i<=(r);++i)
const int N = 1e5+10;
const int mod = 1e9+7;
const int INF = 1e18;
struct node{
int w, l, r;
};
struct SB{
int ti, tal;
};
void solve()
{
int n, m, k;
int ma= 0;
cin >> n >> m;
vector<node> v(n+1);
for (int i = 1; i<=n; i++){
cin >> v[i].w >> v[i].l >> v[i].r;
}
vi pre(n+1), ti(n+1);
sort(v.begin()+1, v.end(), [](node a, node b){
return a.w < b.w;
});
for (int i = 1; i<=n; i++){
pre[i] = pre[i-1]+v[i].w*v[i].l;
ti[i] = ti[i-1]+v[i].l;
}
vector<SB> sb(n+2);
// cout << pre[n] << " " << ti[n] << endl;
for (int i = n; i>=1; i--){
int tp = v[i].r-v[i].l;
sb[i].ti = sb[i+1].ti+tp;
sb[i].tal = sb[i+1].tal + tp*v[i].w;
}
// for (int i = n; i>=1; i--){
// cout << sb[i].ti << " " << sb[i].tal << endl;
// }
for (int i = 1; i<=n; i++){
int val = pre[n]- v[i].w*v[i].l;
int tt = ti[n]-v[i].l;
tt = m-tt;
int l = i-1, r = n+1;
while (l+1 < r){
int mid = (l+r)/2;
if (sb[mid].ti <= tt){
r = mid;
}
else{
l = mid;
}
}
if(r!=i+1){
val += sb[r].tal;
int pp = tt-sb[r].ti;
val+=v[r-1].w*pp;
}else{
val += sb[r].tal;
int pp = tt-sb[r].ti;
val += v[i].w * pp;
}
// cout << val << endl;
ma = max(ma, val);
}
cout << ma << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3808kb
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: 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:
35204500
result:
ok single line: '35204500'
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 3524kb
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:
21525595
result:
wrong answer 1st lines differ - expected: '22000255', found: '21525595'