QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#680406 | #9529. Farm Management | ucup-team3474# | WA | 1ms | 5884kb | C++20 | 1.3kb | 2024-10-26 20:58:33 | 2024-10-26 20:58:34 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1919810;
typedef long long ll;
typedef pair<ll,ll> PII;
ll n,m,k,p;
typedef struct{
ll l,r,len,w;
}Node;
Node e[N];
bool cmp(Node &a,Node &b){
return a.w>b.w;
}
ll s[N],val[N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
ll l,r,w;
scanf("%lld%lld%lld",&w,&l,&r);
e[i]={l,r,r-l,w};
}
sort(e+1,e+1+n,cmp);
ll base=0,ans=0;
for(int i=1;i<=n;i++){
base+=e[i].l*e[i].w;
m-=e[i].l;
}
for(int i=1;i<=n;i++){
s[i]=e[i].len;
val[i]=e[i].len*e[i].w;
s[i]+=s[i-1];
val[i]+=val[i-1];
}
for(int i=1;i<=n;i++){
if(s[i]>=m){
ll tot=val[i]-(s[i]-m)*e[i].w;
ans=tot;
break;
}
}
for(int i=1;i<=n;i++){
ll l=1,r=n;
ll bbase=base-e[i].l*e[i].w;
ll mm=m+e[i].l;
while(l<r){
ll mid=l+r>>1;
ll val=s[mid];
if(mid>=i) val-=e[i].len;
if(val<mm) l=mid+1;
else r=mid;
}
ll vl=s[l],vl2=val[l];
if(l>=i){
vl-=e[i].len;
vl2-=e[i].len*e[i].w;
}
ll tot=bbase+vl2-(vl-mm)*e[l].w;
ans=max(ans,tot);
}
cout<<ans<<endl;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5872kb
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: 5804kb
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: 5884kb
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:
17015002
result:
wrong answer 1st lines differ - expected: '22000255', found: '17015002'