QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#718643#9529. Farm ManagementExile_Code#WA 1ms3860kbC++201.8kb2024-11-06 21:02:062024-11-06 21:02:13

Judging History

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

  • [2024-11-06 21:02:13]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3860kb
  • [2024-11-06 21:02:06]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

#define ll long long 
#define pii pair<ll,ll>
#define endl '\n'
#define vv vector
#define all(x) x.begin()+1,x.end()

#define int ll

#define ft first
#define sd second


struct node
{
    int w,l,r;
    int rest;
    node(int w_=0,int l_=0,int r_=0,int rest_=0):w(w_),l(l_),r(r_),rest(rest_) {}
    friend bool operator<(const node&a,const node&b)
    {
        return a.w>b.w;
    };
};


void solve(){

    int n,m;
    cin>>n>>m;
    vector<node> a(n+1);
    ll sumL=0;
    ll sum=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].w>>a[i].l>>a[i].r;
        sumL+=a[i].l;
        sum+=a[i].l*a[i].w;
        a[i].rest=a[i].r-a[i].l;
    }
    sort(a.begin()+1,a.end());
    ll now=sumL;
    for(int i=1;i<=n;i++)
    {
        if(a[i].rest+now<m)
        {
            a[i].rest=0;
            sum+=a[i].rest*a[i].w;
        }
        else
        {
            a[i].rest-=m-now;
            sum+=(m-now)*a[i].w;
            now=m;
            break;
        }
    }
    vector<int> preR(n+1);
    for(int i=1;i<=n;i++)
    {
        preR[i]=preR[i-1]+a[i].rest;
    }
    vector<int> preW(n+1);
    for(int i=1;i<=n;i++)
    {
        preW[i]=preW[i-1]+(a[i].r-a[i].rest)*a[i].w;
    }
    ll ans=preW[n];
    for(int i=1;i<=n;i++)
    {
        int re=a[i].rest;
        preR[i]+=m-re;
        int l=1,r=i;
        while (l<r)
        {
            int mid=(l+r+1)>>1;
            if(preR[mid]>re)
                r=mid-1;
            else
                l=mid;
        }
        ans=max(ans,preW[l-1]+(re-preR[l-1])*a[l].w);
        preR[i]-=m-re;
    }
    cout<<ans<<"\n";
}
signed main(){

    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    int _=1;
    // cin>>_;
    while(_--)
        solve();


    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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:

31758380

result:

wrong answer 1st lines differ - expected: '35204500', found: '31758380'