QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #692688 | #9529. Farm Management | zhilin# | WA | 0ms | 3936kb | C++14 | 946b | 2024-10-31 14:54:48 | 2024-10-31 14:54:48 |
Judging History
answer
#include<cstdio>
#include<algorithm>
#include<iostream>
#define INF 0x3f3f3f3f
typedef long long ll;
int n;
ll m,ans,ts[100010],ps[100010];
struct crop{
ll w,ex,minn;
bool operator<(const crop &t)const{
return t.w<w;
}
}p[100010];
using std::cin;
int main(){
ll x,y,z;
cin>>n>>m;
for(int i=1;i<=n;i++){
scanf("%lld%lld%lld",&x,&y,&z);
m-=y;
ans+=x*y;
p[i].ex=z-y;
p[i].minn=y;
p[i].w=x;
ts[i]=ts[i-1]+p[i].ex;
ps[i]=ps[i-1]+p[i].ex*p[i].w;
}
std::sort(p+1,p+n+1);
ll sum=ans;
ans+=p[1].w*m;
//printf("%d",ans);
for(int i=n;i>0;i--){
//printf("%d\n",i);
if(ts[i]<=m)break;
m+=p[i].minn;
int l=1,r=n,mid,qwq=n;
while(l<=r){
mid=l+r>>1;
if(ts[mid]>m)qwq=mid,r=mid-1;
else l=mid+1;
}
ans=std::max(ans,sum+ps[qwq]-p[qwq].w*(ts[qwq]-m)-p[i].minn*p[i].w);
}
printf("%lld",ans);
return 0;
}
/*
5 17
2 3 4
6 1 5
8 2 4
4 3 3
7 5 5
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3936kb
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: 3904kb
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:
36874377
result:
wrong answer 1st lines differ - expected: '35204500', found: '36874377'