Submission #937258

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
937258	2024-03-03T17:12:46 Z	Litusiano	Gym Badges (NOI22_gymbadges)	C++17	24 / 100	1503 ms	190364 KB

Main

// #pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math,inline")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,lzcnt,mmx,abm,avx,avx2,fma")
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 1e18;
mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());

bool cmp(pair<int,int> a, pair<int,int> b){
	return a.second-a.first > b.second-b.first;
}

void shuffle(vector<pair<int,int>>& v){
	int n = v.size();
	for(int i = 0; i<3*n; i++){
		int a = rng()%n; int b = rng()%n;
		swap(v[a],v[b]);
	}

}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n; cin>>n;
	vector<pair<int,int>> v(n); for(auto& i : v) cin>>i.first;
	for(auto& i :v) cin>>i.second;
	
	// for(auto x : v) cout<<x.first<<" "<<x.second<<endl;
	if(n > 5000){
		sort(v.begin(),v.end());
		int s = 0;
		int ans = 0;
		for(int i = 0; i<n; i++){
			if(s <= v[i].second){
				s+=v[i].first; ans++;
			}
		}
		cout<<ans<<endl; return 0;
	}
	int mx = 0;
	int MAXN = 1e8;
	MAXN/=(n*n);
	for(int _ = 0; _<MAXN; _++){
		shuffle(v);
		vector<vector<int>> dp(n+1, vector<int>(n+1,inf));
		dp[0][0] = 0;
		for(int i = 1; i<=n; i++){
			for(int j = 0; j<=n; j++){
				dp[i][j] = dp[i-1][j];
				// take i
				if(!j) continue;
	 			int act = dp[i-1][j-1];
				if(act <= v[i-1].second) act+=v[i-1].first;
				else continue;
				dp[i][j] = min(dp[i][j],act);
				// cerr<<i<<" "<<j<<" "<<dp[i-1][j-1]<<" "<<v[i-1].second<<" "<<v[i-1].first<<"  "<<dp[i][j]<<endl;
			}
		}
		for(int i = 0; i<=n; i++){
			// cout<<dp[n][i]<<" ";
			if(dp[n][i] != inf) mx = max(mx,i);
		}
	}
	cout<<mx<<endl;
}

Subtask #1
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1458 ms	436 KB	Output is correct
2	Correct	1423 ms	432 KB	Output is correct
3	Correct	1186 ms	432 KB	Output is correct
4	Correct	1188 ms	428 KB	Output is correct
5	Correct	1170 ms	432 KB	Output is correct
6	Correct	1226 ms	432 KB	Output is correct
7	Correct	1307 ms	436 KB	Output is correct
8	Correct	1233 ms	596 KB	Output is correct
9	Correct	1469 ms	440 KB	Output is correct
10	Correct	1475 ms	436 KB	Output is correct
11	Correct	1503 ms	432 KB	Output is correct
12	Correct	1487 ms	440 KB	Output is correct
13	Correct	1270 ms	432 KB	Output is correct
14	Correct	1215 ms	432 KB	Output is correct
15	Correct	1184 ms	436 KB	Output is correct
16	Correct	1358 ms	436 KB	Output is correct
17	Correct	1312 ms	436 KB	Output is correct
18	Correct	1456 ms	432 KB	Output is correct
19	Correct	1182 ms	440 KB	Output is correct
20	Correct	1176 ms	440 KB	Output is correct

Subtask #2
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	107 ms	8284 KB	Output is correct
2	Correct	111 ms	8024 KB	Output is correct
3	Correct	109 ms	8280 KB	Output is correct
4	Correct	116 ms	8280 KB	Output is correct
5	Correct	110 ms	8280 KB	Output is correct
6	Correct	108 ms	8284 KB	Output is correct
7	Correct	102 ms	8280 KB	Output is correct
8	Correct	128 ms	8284 KB	Output is correct
9	Correct	105 ms	8280 KB	Output is correct
10	Correct	107 ms	8280 KB	Output is correct
11	Correct	98 ms	8284 KB	Output is correct
12	Correct	99 ms	8284 KB	Output is correct
13	Correct	98 ms	8280 KB	Output is correct
14	Correct	97 ms	8284 KB	Output is correct
15	Correct	98 ms	8284 KB	Output is correct
16	Correct	105 ms	8280 KB	Output is correct
17	Correct	113 ms	8284 KB	Output is correct
18	Correct	106 ms	8284 KB	Output is correct
19	Correct	113 ms	8280 KB	Output is correct
20	Correct	104 ms	8260 KB	Output is correct

Subtask #3
0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1458 ms	436 KB	Output is correct
2	Correct	1423 ms	432 KB	Output is correct
3	Correct	1186 ms	432 KB	Output is correct
4	Correct	1188 ms	428 KB	Output is correct
5	Correct	1170 ms	432 KB	Output is correct
6	Correct	1226 ms	432 KB	Output is correct
7	Correct	1307 ms	436 KB	Output is correct
8	Correct	1233 ms	596 KB	Output is correct
9	Correct	1469 ms	440 KB	Output is correct
10	Correct	1475 ms	436 KB	Output is correct
11	Correct	1503 ms	432 KB	Output is correct
12	Correct	1487 ms	440 KB	Output is correct
13	Correct	1270 ms	432 KB	Output is correct
14	Correct	1215 ms	432 KB	Output is correct
15	Correct	1184 ms	436 KB	Output is correct
16	Correct	1358 ms	436 KB	Output is correct
17	Correct	1312 ms	436 KB	Output is correct
18	Correct	1456 ms	432 KB	Output is correct
19	Correct	1182 ms	440 KB	Output is correct
20	Correct	1176 ms	440 KB	Output is correct
21	Incorrect	366 ms	190364 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #4
0 / 49.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1458 ms	436 KB	Output is correct
2	Correct	1423 ms	432 KB	Output is correct
3	Correct	1186 ms	432 KB	Output is correct
4	Correct	1188 ms	428 KB	Output is correct
5	Correct	1170 ms	432 KB	Output is correct
6	Correct	1226 ms	432 KB	Output is correct
7	Correct	1307 ms	436 KB	Output is correct
8	Correct	1233 ms	596 KB	Output is correct
9	Correct	1469 ms	440 KB	Output is correct
10	Correct	1475 ms	436 KB	Output is correct
11	Correct	1503 ms	432 KB	Output is correct
12	Correct	1487 ms	440 KB	Output is correct
13	Correct	1270 ms	432 KB	Output is correct
14	Correct	1215 ms	432 KB	Output is correct
15	Correct	1184 ms	436 KB	Output is correct
16	Correct	1358 ms	436 KB	Output is correct
17	Correct	1312 ms	436 KB	Output is correct
18	Correct	1456 ms	432 KB	Output is correct
19	Correct	1182 ms	440 KB	Output is correct
20	Correct	1176 ms	440 KB	Output is correct
21	Correct	107 ms	8284 KB	Output is correct
22	Correct	111 ms	8024 KB	Output is correct
23	Correct	109 ms	8280 KB	Output is correct
24	Correct	116 ms	8280 KB	Output is correct
25	Correct	110 ms	8280 KB	Output is correct
26	Correct	108 ms	8284 KB	Output is correct
27	Correct	102 ms	8280 KB	Output is correct
28	Correct	128 ms	8284 KB	Output is correct
29	Correct	105 ms	8280 KB	Output is correct
30	Correct	107 ms	8280 KB	Output is correct
31	Correct	98 ms	8284 KB	Output is correct
32	Correct	99 ms	8284 KB	Output is correct
33	Correct	98 ms	8280 KB	Output is correct
34	Correct	97 ms	8284 KB	Output is correct
35	Correct	98 ms	8284 KB	Output is correct
36	Correct	105 ms	8280 KB	Output is correct
37	Correct	113 ms	8284 KB	Output is correct
38	Correct	106 ms	8284 KB	Output is correct
39	Correct	113 ms	8280 KB	Output is correct
40	Correct	104 ms	8260 KB	Output is correct
41	Incorrect	366 ms	190364 KB	Output isn't correct
42	Halted	0 ms	0 KB	-

Submission #937258

Compilation message

Subtask #1 15.0 / 15.0

Subtask #2 9.0 / 9.0

Subtask #3 0 / 27.0

Subtask #4 0 / 49.0

Subtask #1
15.0 / 15.0

Subtask #2
9.0 / 9.0

Subtask #3
0 / 27.0

Subtask #4
0 / 49.0