Submission #992235

#	Time	Username	Problem	Language	Result	Execution time	Memory
992235		inventiontime	Gym Badges (NOI22_gymbadges)	C++17	15 / 100	109 ms	12168 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#define int ll
#define endl '\n' //comment for interactive
#define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
 
#define pb push_back
#define re resize
#define ff first
#define ss second
 
#define all(x) (x).begin(), (x).end()
#define all1(x) (x).begin()+1, (x).end()
#define loop(i, n) for(int i = 0; i < n; i++)
#define loop1(i, n) for(int i = 1; i <= n; i++)
 
#define print(x) cout << #x << ": " << x << endl << flush
 
typedef long long ll;
typedef vector<int> vi;
typedef array<int, 2> ii;
typedef array<int, 3> ti;
typedef vector<ii> vii;
typedef vector<ti> vti;
typedef vector<vi> vvi;
typedef priority_queue<int> pq;
 
template<class T> bool ckmin(T&a, T b) { bool B = a > b; a = min(a, b); return B; }
template<class T> bool ckmax(T&a, T b) { bool B = a < b; a = max(a, b); return B; }
 
const int inf = 1e17;
 
void solve() {
 
    int n; cin >> n;
    vti g(n+1);
    loop1(i, n) cin >> g[i][1]; // x
    loop1(i, n) cin >> g[i][2]; // l
    loop1(i, n) g[i][0] = g[i][1] + g[i][2];
    sort(all1(g));
 
    set<int, greater<int>> st;
    int exp = 0;
    loop1(i, n) {
        if(exp <= g[i][2]) {
            st.insert(g[i][1]);
            exp += g[i][1];
        } else if(exp - *st.begin() <= g[i][2] and *st.begin() > g[i][1]) {
            auto it = st.begin();
            exp -= *it;
            st.erase(it);
            st.insert(g[i][1]);
            exp += g[i][1];
        }
    }

    cout << st.size() << endl;
 
}
 
signed main() {
 
    fast_io;
 
    int t = 1; //cin >> t;
    while(t--)
        solve();
 
    return 0;
 
}

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