Submission #914224

#	Time	Username	Problem	Language	Result	Execution time	Memory
914224		davitmarg	Gym Badges (NOI22_gymbadges)	C++17	100 / 100	184 ms	12244 KiB

Main

/*
DavitMarg
In a honky-tonk,
Down in Mexico
*/
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <random>
#include <chrono>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair    
#define PB push_back
#define all(v) v.begin(), v.end()
#define fastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;

const int N = 500005;

int n;
pair<int, int> a[N];
int ans = 0;

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i].first;

    for (int i = 1; i <= n; i++)
        cin >> a[i].second;

    for (int i = 1; i <= n; i++)
        a[i].second += a[i].first;

    sort(a + 1, a + 1 + n, [](pair<int, int> x, pair<int, int> y) {
        return x.second < y.second;
        });


    priority_queue<int> q;

    for (int i = n; i >= 1; i--)
    {
        q.push(-a[i].first);
        if(a[i-1].second == a[i].second)
			continue;

        int d = a[i].second - a[i - 1].second;
        while (!q.empty() && d)
        {
            int x = -q.top();
            q.pop();

            if (x <= d)
            {
				d -= x;
				ans++;
			}
            else
            {
				x -= d;
				d = 0;
				q.push(-x);
			}
        }
    }

    cout << ans << endl;
}

int main()
{
    fastIO;
    int T = 1;
    //cin >> T;
    while (T--)
    {
        solve();
    }

    return 0;
}

/*


*/

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