QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#694336#9529. Farm ManagementYuLanWA 1ms7064kbC++201.4kb2024-10-31 17:44:062024-10-31 17:44:09

Judging History

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

  • [2024-10-31 17:44:09]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:7064kb
  • [2024-10-31 17:44:06]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
struct node
{
    ll w,l,r;
    node() : w(0), l(0), r(0) {}
    node(ll w1,ll l1,ll r1)
    {
        w = w1;
        l = l1;
        r = r1;
    }
    bool operator < (const node & a) const
    {
        return w > a.w;
    }
};
node b[N];
ll suml[N],sumd[N],sumindex[N],sumLsum[N];
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    ll n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        ll w1,l1,r1;
        cin>>w1>>l1>>r1;
        b[i] = node(w1,l1,r1);
    }
    sort(b+1,b+1+n);
    for(int i=1;i<=n;i++)
    {
        suml[i] = suml[i-1] + b[i].l;
        sumd[i] = sumd[i-1] + (b[i].r - b[i].l)*b[i].w;
        sumindex[i] = sumindex[i-1] + (b[i].r - b[i].l);
        sumLsum[i] = sumLsum[i-1] + b[i].l * b[i].w;
    }
    ll ans = 0;
    for(int i=1;i<=n;i++)
    {
        ll length = m - (suml[n] - suml[i])-suml[i-1];
        ll now = sumLsum[i-1];
        if(sumindex[i-1]<=length)
        {
            now += sumd[i-1] + b[i].w * (length - sumindex[i-1]);
        }else{
            int pos = upper_bound(sumindex,sumindex+i,length) - sumindex - 1;
            now += sumd[pos-1] + (length - sumindex[pos-1])*b[pos].w;
        }
        ans = max(ans,now);
    }
    cout<<ans<<endl;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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:

33742992

result:

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