QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#724986 | #9529. Farm Management | xydCatGirl# | WA | 0ms | 5772kb | C++20 | 2.0kb | 2024-11-08 15:48:00 | 2024-11-08 15:48:01 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
// #define db long double
#define db double
#define pii pair<int,int>
using namespace std;
const int mod=1e9+7,N=2e5+10,inf=1e18;
int n,m;
struct giao{
int l,r,w;
}p[N];
int res=0;
int tot,cnt;
int a[N],b[N];
int wa[N],wb[N];
bool flag[N];
int get_a(int l,int r){
return a[r]-a[l-1];
}
int get_wa(int l,int r){
return wa[r]-wa[l-1];
}
int get_b(int l,int r){
return b[r]-b[l-1];
}
int get_wb(int l,int r){
return wb[r]-wb[l-1];
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
tot=m;
for(int i=1;i<=n;++i){
cin>>p[i].w>>p[i].l>>p[i].r;
tot-=p[i].l;
cnt+=p[i].l;
res+=p[i].l*p[i].w;
}
sort(p+1,p+1+n,[&](giao x,giao y){
return x.w>y.w;
});
int tmp=0;
for(int i=1;i<=n;++i){
a[i]=p[i].r-p[i].l;
b[i]=p[i].r-p[i].l;
if(tot){
if(a[i]<=tot){
tot-=a[i];
b[i]=0;
tmp+=a[i]*p[i].w;
}
else{
b[i]=p[i].r-p[i].l-tot;
tmp+=tot*p[i].w;
tot=0;
}
flag[i]=1;
}
wa[i]=a[i]*p[i].w;
a[i]+=a[i-1];
wa[i]+=wa[i-1];
wb[i]=b[i]*p[i].w;
b[i]+=b[i-1];
wb[i]+=wb[i-1];
}
int out=0;
for(int i=1;i<=n;++i){
if(flag[i])
out=max(out,res+get_wa(1,i-1)+(m-cnt-get_a(1,i-1))*p[i].w);
else{
int l=1,r=i-1,wei=0;
while(l<=r){
int mid=(l+r)>>1;
if(get_b(1,mid)<=p[i].l){
wei=mid;
l=mid+1;
}
else r=mid-1;
}
out=max(out,get_wb(1,wei-1)+res+tmp-p[i].l*p[i].w+(p[i].l-get_b(1,wei-1))*p[wei].w);
}
}
cout<<out<<endl;
return 0;
}
/*
*/
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 5772kb
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: 5700kb
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:
34950156
result:
wrong answer 1st lines differ - expected: '35204500', found: '34950156'