Submission #787261

#	Time	Username	Problem	Language	Result	Execution time	Memory
787261		Ozy	Gym Badges (NOI22_gymbadges)	C++17	42 / 100	24 ms	852 KiB

Main

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)
#define pll pair<lli,lli>

#define MAX 5000
//para el arr
#define exp first
#define umbral second

lli n,cont,a,b;
pll arr[MAX+2],act,res[MAX+2];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    rep(i,1,n) cin >> arr[i].first;
    rep(i,1,n) cin >> arr[i].second;
    sort(arr+1, arr+n+1);

    res[0] = {0,(1ll<<60)};
    cont = 0;
    rep(Q,1,n) {

        act = arr[Q];
        lli pos = -1;
        lli mejor = -1;
        lli MIN = (1ll<<60);
        repa(i,cont,0) {

            a = act.umbral - res[i].exp;
            if (a < 0) {
                if (act.exp > res[i].umbral) break;
                continue;
            }

            b = min(MIN,a);
            if (b > mejor) {
                mejor = b;
                pos = i+1;
            }

            MIN = min(MIN,res[i].umbral-act.exp);
            if (act.exp > res[i].umbral) break;

            //debugsl(a);
            //debugsl(b);
            //debug(MIN);
        }

        //debugsl(act.exp);
        //debugsl(act.umbral);
        //debug(pos);

        if (pos != -1) {
            cont++;
            pll cambio = {res[pos-1].exp + act.exp,(act.umbral - res[pos-1].exp)};
            rep(i,pos,cont) {
                res[i].exp += act.exp;
                res[i].umbral -= act.exp;
                swap(cambio,res[i]);
            }
        }

        //rep(i,1,cont) debugsl(res[i].exp);
        //cout << endl;
        //rep(i,1,cont) debugsl(res[i].umbral);
        //cout << endl;
    }

    cout << cont;

    return 0;
}

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