QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#717491 | #9529. Farm Management | nihaoakeke1 | WA | 1ms | 5752kb | C++14 | 3.3kb | 2024-11-06 18:06:41 | 2024-11-06 18:06:50 |
Judging History
answer
//#include<bits/stdc++.h>
//#define int long long
//#define mod 998244353ll
//#define pii pair<int,int>
//#define fi first
//#define se second
//#define mems(x,y) memset(x,y,sizeof(x))
//#define pb push_back
//#define db double
//using namespace std;
//const int maxn=200010;
//const int inf=1e18;
//inline int read(){
// int x=0,f=1;
// char ch=getchar();
// while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
// while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch-48);ch=getchar();}
// return x*f;
//}
//bool Mbe;
//
//int n,m,ans;
//struct nd{
// int a,l,r;
//}a[maxn];
//int t[maxn],f[maxn],g[maxn];
//void work(){
// n=read();m=read();int mx=0;
// for(int i=1;i<=n;i++)a[i]={read(),read(),read()};
// sort(a+1,a+n+1,[&](nd u,nd v){return u.a>v.a;});
// // for(int i=1;i<=n;i++)cout<<a[i].a<<" "<<a[i].l<<" "<<a[i].r<<"\n";
// int sum=0,cur=0;
// for(int i=1;i<=n;i++)t[i]=a[i].l,sum+=a[i].a*a[i].l,cur+=a[i].l;
// ans=sum+a[1].a*(m-cur);
// for(int i=1;i<=n;i++){
// int d=min(m-cur,a[i].r-a[i].l);
// t[i]+=d,sum+=a[i].a*d,cur+=d;
// }
//
// // cout<<ans<<" "<<cur<<"\n";
// for(int i=1;i<=n;i++){
// f[i]=f[i-1]+(a[i].r-t[i]);
// g[i]=g[i-1]+(a[i].r-t[i])*a[i].a;
// }
// for(int i=1;i<=n;i++){
// int d=m-cur+t[i];
// int p=upper_bound(f+1,f+n+1,d)-f-1;
// //cout<<sum<<"asdasdadasdasdasd\n";
// // cout<<ans<<" "<<i<<" "<<p<<" "<<sum-t[i]*a[i].a+g[p]+(p<i?(d-f[p])*a[p+1].a:(d-f[p])*a[i].a)<<"\n";
// ans=max(ans,sum-t[i]*a[i].a+g[p]+(p<i?(d-f[p])*a[p+1].a:(d-f[p])*a[i].a));
// if(ans==109){cout<<i<<"\n";}
// }
// printf("%lld\n",ans);
//}
//
//// \
//444
//
//bool Med;
//int T;
//signed main(){
//// freopen(".in","r",stdin);
//// freopen(".out","w",stdout);
//
//// ios::sync_with_stdio(0);
//// cin.tie(0);cout.tie(0);
//
//// cerr<<(&Mbe-&Med)/1048576.0<<" MB\n";
//
// T=1;
// while(T--)work();
//}
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=5e5+100;
struct node{
int w,l,r;
}p[maxn];
bool cmp(node x,node y){
if(x.w!=y.w) return x.w>y.w;
else return x.l>y.l;
}
int f[maxn];
int val[maxn];
int ti[maxn];
signed main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>p[i].w>>p[i].l>>p[i].r;
}
sort(p+1,p+1+n,cmp);
int sum=0; //最小价值
int ans=0;
int alltime=0;
for(int i=1;i<=n;i++){
ti[i]=p[i].l;
sum+=p[i].w*p[i].l;
alltime+=p[i].l;
}
ans=sum+p[1].w*(m-alltime); //当下的最大值
for(int i=1;i<=n;i++)
{
int temp=min(m-alltime,p[i].r-p[i].l);
ti[i]+=temp;
sum+=temp*p[i].w;
alltime+=temp;
}
for(int i=1;i<=n;i++)
{
f[i]=f[i-1]+(p[i].r-ti[i]); //继续能增加的时间
val[i]=val[i-1]+(p[i].r-ti[i])*p[i].w; //继续能增加的价值
}
for(int i=1;i<=n;i++)
{
//枚举每一个放弃时间限制
int d=m-alltime+ti[i];
int idx= upper_bound(f+1,f+1+n,d)-f-1;
int cal=sum-p[i].w*ti[i]+val[idx];
if(idx<i)
{
cal+=p[idx].w*(d-f[idx]);
}else{
cal+=p[i].w+(d-f[idx]);
}
ans=max(ans,cal);
}
cout<<ans<<"\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5680kb
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: 1ms
memory: 5752kb
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'