제출 #1353477

#제출 시각아이디문제언어결과실행 시간메모리
1353477silverwolfGym Badges (NOI22_gymbadges)C++20
100 / 100
133 ms6516 KiB
/*
tags: usaco | codeforces | centroid_decomposition 
*/
 
#include <bits/stdc++.h>
using namespace std;
using namespace std::complex_literals;
 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
 
#define ll long long
#define mask(i) (1 << (i))
#define bit(x, i)  (((x) >> (i)) & 1)
#define onbit(x, i) ((x) = (x) | mask(i))
#define offbit(x, i) ((x) = (x) & (~mask(i)))
#define pcount(i) __builtin_popcount(i)
#define bctz(i) __builtin_ctz(i)
#define all(v) v.begin(), v.end()
#define all1(v) v.begin()+1, v.end()
#define sz(v) (int)v.size()
#define sqr(x) ((x) * (x))
#define FOR(i,l,r) for(int i=(l);i<=(r);i++)
#define FORD(i,l,r) for(int i=(l);i>=(r);i--)
#define REP(i, r) for(int i=0;i<(r);i++)
#define BITSET(size, x) std::bitset<size + 1>(x).to_string().c_str()
#define vi vector<int>
#define vii vector<vector<int>>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define complex complex<long double>
#define ite std::vector<int>::iterator
// #define int ll
template <class T> bool minimize(T& x,T y) {
    if (x > y) x = y; else return 0; return 1;
}
template <class T> bool maximize(T& x,T y) {
    if (x < y) x = y; else return 0; return 1;
}
// const ll INF = 1e9 + 2;
bool cmp(const pii& a, const pii& b) {
	return a.first + a.second < b.first + b.second;
}
inline void solve()
{
	int n;
	cin  >> n;
	pii a[n+1];
	for(int i = 1; i <= n;i++) {
		cin >> a[i].first;
	}
	for(int i = 1; i <= n;i++) {
		cin >> a[i].second;
	}
	sort(a + 1, a + n + 1, cmp);
	priority_queue<int, vi> maxqueue;
	ll s = 0;
	for(int i = 1; i <= n; i++) {
		s += a[i].first;
		maxqueue.push(a[i].first);
		if(s > a[i].first + a[i].second) {
			s -= maxqueue.top();
			maxqueue.pop();
		}
	}
	cout << maxqueue.size() << '\n';
}
 
int main() {
	#ifndef ONLINE_JUDGE
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout); 
    #endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...