oj.uz

Submission #886529

# Submission time Handle Problem Language Result Execution time Memory
886529 2023-12-12T09:33:55 Z vjudge1 Gym Badges (NOI22_gymbadges) C++17
9 / 100
 181 ms 33948 KB 
#include <bits/stdc++.h>
using namespace std;
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define sp " "
#define endl "\n"
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second 
#define N 500005
#define int long long

const int INF = 1e9 + 7;

int x[N], l[N];

int32_t main(){
	//fileio();
	fastio();


	int n;
	cin>>n;
	for (int i = 1; i <= n; i++){
		cin>>x[i];
	}
	for (int i = 1; i <= n; i++){
		cin>>l[i];
	}

	vector<int> v(n, 0);
	iota(v.begin(), v.end(), 1);
	sort(v.begin(), v.end(), [&](int a, int b){
		if (x[a] == x[b]) return l[a] < l[b];
		return x[a] < x[b];
	});

	int sum = 0;
	int ans = 0;
	multiset<pii> maks;
	for (auto i : v){
		if (sum <= l[i]){
			sum += x[i];
			ans++;
			maks.insert({l[i] + x[i], x[i]});
			continue;
		}
		int tmp = 0;
		auto it = maks.rbegin();
		while(it != maks.rend() && it->st + tmp >= sum + x[i]){
			tmp -= it->nd;
			it++;
			if (sum <= l[i] + tmp){
				sum += x[i];
				ans++;
				maks.insert({l[i] + x[i], x[i]});
				break;
			}
		}
		
	}
	//cout<<endl;
	cout<<ans<<endl;
	cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
}

Subtask #1
0 / 15.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 12176 KB Output is correct
2 Correct 129 ms 17408 KB Output is correct
3 Correct 127 ms 17308 KB Output is correct
4 Correct 127 ms 17472 KB Output is correct
5 Correct 127 ms 17232 KB Output is correct
6 Correct 130 ms 18020 KB Output is correct
7 Correct 122 ms 16980 KB Output is correct
8 Correct 127 ms 17744 KB Output is correct
9 Correct 129 ms 18080 KB Output is correct
10 Correct 138 ms 18576 KB Output is correct
11 Correct 156 ms 30296 KB Output is correct
12 Correct 178 ms 33104 KB Output is correct
13 Correct 160 ms 31952 KB Output is correct
14 Correct 166 ms 33104 KB Output is correct
15 Correct 181 ms 33948 KB Output is correct
16 Correct 131 ms 21116 KB Output is correct
17 Correct 138 ms 22100 KB Output is correct
18 Correct 141 ms 22828 KB Output is correct
19 Correct 130 ms 20224 KB Output is correct
20 Correct 132 ms 18832 KB Output is correct

Subtask #3
0 / 27.0

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

Subtask #4
0 / 49.0

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