oj.uz

Submission #886438

# Submission time Handle Problem Language Result Execution time Memory
886438 2023-12-12T07:07:53 Z vjudge1 Gym Badges (NOI22_gymbadges) C++17
9 / 100
 157 ms 17212 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,abm,mmx,sse4.2,fma,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;

#define int uint64_t
#define PB push_back
#define sqr(a) ((a)*(a))
#define I insert
#define F first
#define S second

bool cmp(pair<int,int> const&a, pair<int,int> const&b) {
	return make_pair(a.S, a.F) < make_pair(b.S, b.F);
}

int32_t main() {
	cin.tie(0)->sync_with_stdio(0);
	int n;
	cin>>n;
	vector<pair<int,int>> a(n);
	for(int i=0; i<n; i++) cin>>a[i].S;
	for(int i=0; i<n; i++) cin>>a[i].F;
	sort(a.begin(), a.end());
	if(a[0].F==a[n-1].F) {
		sort(a.begin(), a.end(), cmp);
		int ans = 0, cur = 0;
		for(int i=0; i<n; i++) {
			if(cur <= a[0].F) {
				cur += a[i].S;
				ans++;
			}
			else {
				cout<<ans<<'\n';
				return 0;
			}
		}
		cout<<ans<<'\n';
		return 0;
	}
	vector<int> dp(n+1, UINT64_MAX);
	dp[0] = 0;
	for(int i=0; i<n; i++) {
		for(int j=n; j>0; j--) {
			dp[j] = min((dp[j-1]<=a[i].F)?(dp[j-1] + a[i].S):UINT64_MAX, dp[j]);
		}
	}
	for(int i=n; i>=0; i--) {
		if(dp[i]!=UINT64_MAX){
			cout<<i<<'\n';
			break;
		}
	}
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 17040 KB Output is correct
2 Correct 153 ms 17092 KB Output is correct
3 Correct 153 ms 17104 KB Output is correct
4 Correct 153 ms 16964 KB Output is correct
5 Correct 155 ms 17212 KB Output is correct
6 Correct 148 ms 16468 KB Output is correct
7 Correct 151 ms 15952 KB Output is correct
8 Correct 157 ms 16468 KB Output is correct
9 Correct 150 ms 16472 KB Output is correct
10 Correct 151 ms 16316 KB Output is correct
11 Correct 139 ms 15444 KB Output is correct
12 Correct 139 ms 15444 KB Output is correct
13 Correct 142 ms 15416 KB Output is correct
14 Correct 141 ms 15436 KB Output is correct
15 Correct 138 ms 15444 KB Output is correct
16 Correct 145 ms 15444 KB Output is correct
17 Correct 148 ms 15440 KB Output is correct
18 Correct 150 ms 15372 KB Output is correct
19 Correct 146 ms 15292 KB Output is correct
20 Correct 154 ms 15284 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -