QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#678615 | #9529. Farm Management | ucup-team3661# | WA | 0ms | 3732kb | C++20 | 1.6kb | 2024-10-26 15:32:44 | 2024-10-26 15:32:45 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(){
ll N,M;cin>>N>>M;
vector<tuple<ll,ll,ll>>W(N);
for(auto&[w,l,r]:W)cin>>w>>l>>r;
sort(W.rbegin(),W.rend());
vector<ll>use(N),rem(N);
ll rem_time=M,tmp_val=0;
for(int i=0;i<N;i++){
auto[w,l,r]=W[i];
tmp_val+=l*w;
use[i]=l;
rem[i]=r-l;
rem_time-=use[i];
}
for(int i=0;i<N;i++){
auto[w,l,r]=W[i];
if(rem[i]<=rem_time){
tmp_val+=rem[i]*w;
rem_time-=rem[i];
use[i]+=rem[i];
rem[i]=0;
}else{
tmp_val+=rem_time*w;
rem[i]-=rem_time;
use[i]+=rem_time;
rem_time=0;
}
if(rem_time==0)break;
}
assert(rem_time==0);
vector<ll>pref_rem(N+1),pref_val(N+1);
for(int i=0;i<N;i++){
auto[w,l,r]=W[i];
pref_rem[i+1]=pref_rem[i]+rem[i];
pref_val[i+1]=pref_val[i]+rem[i]*w;
}
ll ans=tmp_val;
for(int i=0;i<N;i++){
auto[w,l,r]=W[i];
if(rem[i]==0)continue;
//使う時間を0にする
ll new_rem=use[i];
ll res=tmp_val-use[i]*w;
//これを上から分配する
int lo=-1,hi=i+1;
while(hi-lo>1){
int mid=(hi+lo)/2;
if(pref_rem[mid]<=new_rem)lo=mid;
else hi=mid;
}
ll new_rem2=new_rem-pref_rem[lo];
assert(new_rem2>=0);
res+=pref_val[lo];
//余った時間をloに割り当てる
res+=new_rem2*get<0>(W[lo]);
if(lo<i)assert(new_rem2<=rem[lo]);
ans=max(ans,res);
}
{
ll res=0;
ll rem_time=M;
for(int i=1;i<N;i++){
auto[w,l,r]=W[i];
res+=l*w;
rem_time-=l;
}
{
auto[w,l,r]=W[0];
res+=rem_time*w;
}
ans=max(ans,res);
}
cout<<ans<<endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3452kb
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: 3732kb
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'