QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#724986#9529. Farm ManagementxydCatGirl#WA 0ms5772kbC++202.0kb2024-11-08 15:48:002024-11-08 15:48:01

Judging History

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

  • [2024-11-08 15:48:01]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:5772kb
  • [2024-11-08 15:48:00]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
// #define db long double
#define db double
#define pii pair<int,int>
using namespace std;
const int mod=1e9+7,N=2e5+10,inf=1e18;
int n,m;
struct giao{
    int l,r,w;
}p[N];
int res=0;
int tot,cnt;
int a[N],b[N];
int wa[N],wb[N];
bool flag[N];
int get_a(int l,int r){
    return a[r]-a[l-1];
}
int get_wa(int l,int r){
    return wa[r]-wa[l-1];
}
int get_b(int l,int r){
    return b[r]-b[l-1];
}
int get_wb(int l,int r){
    return wb[r]-wb[l-1];
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    tot=m;
    for(int i=1;i<=n;++i){
        cin>>p[i].w>>p[i].l>>p[i].r;
        tot-=p[i].l;
        cnt+=p[i].l;
        res+=p[i].l*p[i].w;
    }
    sort(p+1,p+1+n,[&](giao x,giao y){
        return x.w>y.w; 
    });
    int tmp=0;
    for(int i=1;i<=n;++i){
        a[i]=p[i].r-p[i].l;
        b[i]=p[i].r-p[i].l;
        if(tot){
            if(a[i]<=tot){
                tot-=a[i];
                b[i]=0;   
                tmp+=a[i]*p[i].w;
            }
            else{
                b[i]=p[i].r-p[i].l-tot;
                tmp+=tot*p[i].w;
                tot=0;
            }
            flag[i]=1;
        }
        wa[i]=a[i]*p[i].w;
        a[i]+=a[i-1];
        wa[i]+=wa[i-1];
        wb[i]=b[i]*p[i].w;
        b[i]+=b[i-1];
        wb[i]+=wb[i-1];
    }
    int out=0;
    for(int i=1;i<=n;++i){
        if(flag[i])
            out=max(out,res+get_wa(1,i-1)+(m-cnt-get_a(1,i-1))*p[i].w);
        else{
            int l=1,r=i-1,wei=0;
            while(l<=r){
                int mid=(l+r)>>1;
                if(get_b(1,mid)<=p[i].l){
                    wei=mid;
                    l=mid+1;
                }
                else r=mid-1;
            }    
            out=max(out,get_wb(1,wei-1)+res+tmp-p[i].l*p[i].w+(p[i].l-get_b(1,wei-1))*p[wei].w);
        }
    }   
    cout<<out<<endl;
    return 0;
}
/*
*/

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 5772kb

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: 5700kb

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'