QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#680406#9529. Farm Managementucup-team3474#WA 1ms5884kbC++201.3kb2024-10-26 20:58:332024-10-26 20:58:34

Judging History

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

  • [2024-10-26 20:58:34]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5884kb
  • [2024-10-26 20:58:33]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1919810;
typedef long long ll;
typedef pair<ll,ll> PII;
ll n,m,k,p;

typedef struct{
    ll l,r,len,w;
}Node;

Node e[N];

bool cmp(Node &a,Node &b){
    return a.w>b.w;
}

ll s[N],val[N];

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        ll l,r,w;
        scanf("%lld%lld%lld",&w,&l,&r);
        e[i]={l,r,r-l,w};
    }
    sort(e+1,e+1+n,cmp);
    ll base=0,ans=0;
    
    for(int i=1;i<=n;i++){
        base+=e[i].l*e[i].w;
        m-=e[i].l;
    }
    for(int i=1;i<=n;i++){
        s[i]=e[i].len;
        val[i]=e[i].len*e[i].w;
        s[i]+=s[i-1];
        val[i]+=val[i-1];
    }
    for(int i=1;i<=n;i++){
        if(s[i]>=m){
            ll tot=val[i]-(s[i]-m)*e[i].w;
            ans=tot;
            break;
        }
    }
    for(int i=1;i<=n;i++){
        ll l=1,r=n;
        ll bbase=base-e[i].l*e[i].w;
        ll mm=m+e[i].l;
        while(l<r){
            ll mid=l+r>>1;
            ll val=s[mid];
            if(mid>=i) val-=e[i].len;
            if(val<mm) l=mid+1;
            else r=mid;
        }
        ll vl=s[l],vl2=val[l];
        if(l>=i){
            vl-=e[i].len;
            vl2-=e[i].len*e[i].w;
        }
        ll tot=bbase+vl2-(vl-mm)*e[l].w;
        ans=max(ans,tot);
    }
    cout<<ans<<endl;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5872kb

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: 0
Accepted
time: 0ms
memory: 5804kb

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:

35204500

result:

ok single line: '35204500'

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 5884kb

input:

15 32
835418 2 3
178262 1 3
527643 2 2
519710 1 1
774544 3 3
82312 1 1
808199 1 1
809396 1 3
255882 1 3
80467 1 3
874973 1 3
813965 1 2
198275 1 2
152356 1 3
802055 1 1

output:

17015002

result:

wrong answer 1st lines differ - expected: '22000255', found: '17015002'