Submission #1151166

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151166		vicvic	Gym Badges (NOI22_gymbadges)	C++20	100 / 100	115 ms	12476 KiB

Main

#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <set>
#include <stack>
#include <cstdint>
#include <queue>
#define int long long
using namespace std;
const int NMAX=5e5;
int n, cnt;
priority_queue <int> coada;
struct what
{
    int x, l;
} gym[NMAX+5];
int32_t main ()
{
    ios :: sync_with_stdio (0);
    cin.tie (nullptr);
    cin >> n;
    for (int i=1;i<=n;i++)
    {
        cin >> gym[i].x;
    }
    for (int i=1;i<=n;i++)
    {
        cin >> gym[i].l;
        gym[i].l+=gym[i].x;
    }
    sort (gym+1, gym+n+1, [] (what a, what b) {return a.l<b.l;});
    int s=0;
    for (int i=1;i<=n;i++)
    {
        if (s+gym[i].x<=gym[i].l)
        {
            s+=gym[i].x;
            coada.push (gym[i].x);
        }
        else
        {
            int val=coada.top();
            if (val>gym[i].x)
            {
                s-=val;
                s+=gym[i].x;
                coada.pop ();
                coada.push (gym[i].x);
            }
        }
    }
    cout << coada.size();
    return 0;
}

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