QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#706198 | #9529. Farm Management | Cocoder | WA | 0ms | 5672kb | C++14 | 1.2kb | 2024-11-03 09:17:22 | 2024-11-03 09:17:22 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
const int N=1e5+10;
struct crop
{
ll l,r,w;
}C[N];
ll suml[N],sumr[N],sumlw[N],sumw[N];
int n,Res;
ll m,ans=0;
bool cmp(crop a,crop b) {return a.w>b.w;}
void calc(int x)
{
int res=Res+C[x].l;
ll ret=sumlw[n]-C[x].l*C[x].w;
if(x==1)
{
ret+=res*C[1].w;
ans=max(ret,ans);
return ;
}
int l=1,r=n+1;
while(r-l>1)
{
int mid=(l+r)>>1;
if(sumr[mid]-suml[mid]<=res) l=mid;
else r=mid;
}
if(l>=x) l=x-1;
ret+=sumw[l];
res-=sumr[l]-suml[l];
ret+=res*C[x].w;
ans=max(ret,ans);
return ;
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>C[i].w>>C[i].l>>C[i].r;
sort(C+1,C+n+1,cmp);
for(int i=1;i<=n;i++)
{
suml[i]=suml[i-1]+C[i].l,sumr[i]=sumr[i-1]+C[i].r;
sumlw[i]=sumlw[i-1]+C[i].l*C[i].w;
sumw[i]=sumw[i-1]+C[i].w*(C[i].r-C[i].l);
}
//for(int i=1;i<=n;i++) cout<<sumw[i]<<endl;
Res=m-suml[n];
for(int i=1;i<=n;i++) calc(i);
cout<<ans;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 5664kb
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: 5672kb
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:
36066030
result:
wrong answer 1st lines differ - expected: '35204500', found: '36066030'