QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#717491#9529. Farm Managementnihaoakeke1WA 1ms5752kbC++143.3kb2024-11-06 18:06:412024-11-06 18:06:50

Judging History

你现在查看的是最新测评结果

  • [2024-11-06 18:06:50]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5752kb
  • [2024-11-06 18:06:41]
  • 提交

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'