QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#687406 | #9529. Farm Management | Albert711 | WA | 1ms | 3804kb | C++20 | 1.6kb | 2024-10-29 18:52:25 | 2024-10-29 18:52:26 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define db double
const int mod=1e9+7;
const int N=2e5+5;
struct info{
int l,r,v;
bool operator<(const info&a)const{
return v>a.v;
}
};
void abt() {
int n,m;
cin>>n>>m;
vector<info> a(n+1);
for(int i=1;i<=n;i++){
cin>>a[i].v>>a[i].l>>a[i].r;
}
sort(a.begin()+1,a.begin()+1+n);
// for(int i=1;i<=n;i++){
// cout<<a[i].v<<' '<<a[i].l<<' '<<a[i].r<<endl;
// }
int ans=0;
int al=0;
int cnt=0;
for(int i=1;i<=n;i++){
al+=a[i].l;
cnt+=a[i].l*a[i].v;
}
ans=max(ans,cnt+(m-al)*a[1].v);
int res=m-al;
vector<int> pre(n+1);
vector<int> prv(n+1);
for(int i=1;i<=n;i++){
pre[i]=pre[i-1]+a[i].r-a[i].l;
}
for(int i=1;i<=n;i++){
prv[i]=prv[i-1]+(a[i].r-a[i].l)*a[i].v;
}
// for(int i=1;i<=n;i++){
// cout<<pre[i]<<' '<<prv[i]<<endl;
// }
// cout<<cnt<<' '<<res<<'\n';
for(int i=2;i<=n;i++){
int tmp=res+a[i].l;
int cc=0;
int pos=lower_bound(pre.begin()+1,pre.begin()+1+i,res)-pre.begin();
// cout<<"11 "<<i<<' '<<pos<<' ';
cc=prv[pos-1];
tmp-=pre[pos-1];
cc+=tmp*a[pos].v;
cc+=cnt-a[i].v*a[i].l;
// cout<<cc<<endl;
ans=max(ans,cc);
}
cout<<ans<<'\n';
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
cout<<fixed<<setprecision(9);
int T=1;
// cin>>T;
while(T--) abt();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3804kb
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: 3584kb
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:
35277263
result:
wrong answer 1st lines differ - expected: '35204500', found: '35277263'