Submission #1153981

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153981		AndrijaM	Gym Badges (NOI22_gymbadges)	C++20	100 / 100	117 ms	12480 KiB

Main

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define endl '\n'

const int maxn=5e5+10;

struct S
{
    int x;
    int l;
};
S a[maxn];

bool cmp(S a,S b)
{
    if(a.l==b.l)
    {
        return a.x<b.x;
    }
    return a.l<b.l;
}

signed main()
{
    ios::sync_with_stdio(0);
    int n;
    cin>>n;
    priority_queue<int>Q;
    for(int i=0;i<n;i++)
    {
        cin>>a[i].x;
    }
    for(int i=0;i<n;i++)
    {
        cin>>a[i].l;
        a[i].l+=a[i].x;
    }
    sort(a,a+n,cmp);
    int sum=0;
    for(int i=0;i<n;i++)
    {
        ///cout<<a[i].x<<" "<<a[i].l<<endl;
        if(sum+a[i].x<=a[i].l)
        {
            sum+=a[i].x;
            Q.push(a[i].x);
            continue;
        }
        int mx=Q.top();
        if(mx>a[i].x)
        {
            Q.pop();
            Q.push(a[i].x);
            sum-=mx;
            sum+=a[i].x;
        }
    }
    cout<<Q.size()<<endl;
    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 9 / 9
• Subtask 3: 27 / 27
• Subtask 4: 49 / 49