QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#717232#9529. Farm ManagementzhensamaWA 0ms3828kbC++201.3kb2024-11-06 17:17:552024-11-06 17:17:56

Judging History

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

  • [2024-11-06 17:17:56]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3828kb
  • [2024-11-06 17:17:55]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
using namespace std;
const int N=1e5+10;
struct node
{
    int w,l,r,sum,diff,Sum;
}a[N];
bool cmp(node a,node b)
{
    return a.w>b.w||a.w==b.w&&a.l<b.l;
}
void solve()
{
    int n,m;cin>>n>>m;
    int L[n+1]={0},R[n+1]={0},S=0;
    for(int i=1;i<=n;i++)
    {
         cin>>a[i].w>>a[i].l>>a[i].r;
        a[i].sum=a[i].w*a[i].l;
        a[i].diff=a[i].r-a[i].l;
        a[i].Sum=a[i].diff*a[i].w;
        S+=a[i].sum;
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        L[i]=L[i-1]+a[i].l;
        R[i]=R[i-1]+a[i].r;
    }
    //cout<<L[n]<<" "<<R[n]<<'\n';
    vector<int> diff(n+10,0),Sum(n+10,0);
    for(int i=1;i<=n;i++)
    {
        diff[i]=diff[i-1]+a[i].diff;
        Sum[i]=Sum[i-1]+a[i].Sum;
    }
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        int ans=S;
        int t=L[n];
        ans-=a[i].sum;
        t-=a[i].l;
        int bin=upper_bound(diff.begin(),diff.begin()+i-1,m-t)-diff.begin();
        //cout<<bin<<" ";
           ans+=Sum[bin]+a[bin+1].w*(m-t-diff[bin]);
        //cout<<ans<<" ";
        sum=max(sum,ans);
    }
    cout<<sum<<'\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t=1;//cin>>t;
    while(t--)
        solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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:

35309054

result:

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