oj.uz

Submission #937260

# Submission time Handle Problem Language Result Execution time Memory
937260 2024-03-03T17:14:12 Z Litusiano Gym Badges (NOI22_gymbadges) C++17
9 / 100
 2000 ms 8284 KB 
// #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 + 5e7;
	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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2052 ms 348 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 8284 KB Output is correct
2 Correct 117 ms 8260 KB Output is correct
3 Correct 118 ms 8284 KB Output is correct
4 Correct 108 ms 8280 KB Output is correct
5 Correct 121 ms 8284 KB Output is correct
6 Correct 123 ms 8280 KB Output is correct
7 Correct 103 ms 8284 KB Output is correct
8 Correct 105 ms 8280 KB Output is correct
9 Correct 106 ms 8284 KB Output is correct
10 Correct 129 ms 8280 KB Output is correct
11 Correct 103 ms 8284 KB Output is correct
12 Correct 105 ms 8284 KB Output is correct
13 Correct 115 ms 8284 KB Output is correct
14 Correct 97 ms 8280 KB Output is correct
15 Correct 99 ms 8284 KB Output is correct
16 Correct 110 ms 8284 KB Output is correct
17 Correct 105 ms 8284 KB Output is correct
18 Correct 108 ms 8284 KB Output is correct
19 Correct 109 ms 8284 KB Output is correct
20 Correct 110 ms 8028 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2052 ms 348 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2052 ms 348 KB Time limit exceeded
2 Halted 0 ms 0 KB -