Submission #1313119

#TimeUsernameProblemLanguageResultExecution timeMemory
1313119sakuda00Gym Badges (NOI22_gymbadges)C++20
0 / 100
2094 ms16528 KiB
#include <iostream>
#include <vector>
#include <iomanip>
#include <map>
#include <set>
#include <numeric>
#include <queue>
#include <deque>
#include <algorithm>
#include <stack>
#include <unordered_map>
using namespace std;
using ll = long long;
ll inf = (1LL << 60);
void solve1(int N, vector<ll> X, vector<ll> L) {
	vector<pair<ll, ll>> st;
	for (int i = 0;i < N;i++) st.push_back({L[i], X[i]});
	vector<ll> dp(N + 1, inf);
	sort(st.begin(),st.end());
	dp[0] = 0;
	for (int i = 0;i < N;i++) {
		vector<ll> ndp(N + 1, inf);
		for (int j = 0;j <= N;j++) {
			ndp[j] = min(ndp[j], dp[j]);

			if (dp[j] != inf && dp[j] <= st[i].first && j+1 <= N) ndp[j + 1] = min(ndp[j + 1], dp[j] + st[i].second);
		}
		swap(dp, ndp);
	}
	for (int i = N;i >= 0;i--) {
		if (dp[i] != inf) {
			cout << i << endl;
			return;
		}
	}
}
int solve2(int N, vector<ll>& X, vector<ll>& L) {
	vector<pair<ll, ll>> st;
	for (int i = 0;i < N;i++) {
		st.push_back({L[i], X[i]});

	}
	sort(st.begin(),st.end());
	int res = 0;
	for (int bit = 0;bit < (1<<N);bit++) {
		ll now = 0;
		int sc = 0;
		bool flg = true;
		for (int i = 0;i < N;i++) {
			if (bit & (1 << i)) {
				if (now <= st[i].first) {
					now += st[i].second;
					sc++;
				} else {
					flg = false;break;
				}
			}
		}
		if (flg) res = max(res, sc);
	}
	return res;
}
int naive3(int N,vector<ll> X, vector<ll> L) {
	sort(X.begin(),X.end());
	ll l = L[0];
	int sc = 0;
	ll now = 0;
	for (int i = 0;i < N;i++) {
		if (now <= l) {
			now += X[i];
			sc++;
		}
	}
	return sc;
}
int main() {
	int N;cin >> N;
	vector<ll> X(N), L(N);
	for (int i = 0;i < N;i++) cin >> X[i];
	for (int i = 0;i < N;i++) cin >> L[i];
	bool flg = true;
	for (int i = 0;i < N;i++) if (L[i] != L[0]) flg = false;
	if (flg) {
	///	cout <<"NV3" << endl;
		cout << max(naive3(N, X, L), solve2(N, X, L)) << endl;
		//return 0;
	}
	if (N <= 10) {
		solve2(N, X, L);
		return 0;
	}
	if (N <= 5000) {
		solve1(N, X, L);
		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...