Submission #1313115

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313115		sakuda00	Gym Badges (NOI22_gymbadges)	C++20	9 / 100	320 ms	16056 KiB

Main

#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;
		}
	}
}
void 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);
	}
	cout << res << endl;
}
void 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++;
		}
	}
	cout << sc << endl;
}
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) {
		naive3(N, X, L);
		return 0;
	}
	if (N <= 10) {
		solve2(N, X, L);
		return 0;
	}
	if (N <= 5000) {
		solve1(N, X, L);
		return 0;
	}

}

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