oj.uz

Submission #886526

# Submission time Handle Problem Language Result Execution time Memory
886526 2023-12-12T09:31:25 Z vjudge1 Gym Badges (NOI22_gymbadges) C++17
9 / 100
 171 ms 34396 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 (tmp <= l[i]){
				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 2396 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 2512 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 17608 KB Output is correct
2 Correct 129 ms 17488 KB Output is correct
3 Correct 127 ms 17488 KB Output is correct
4 Correct 129 ms 17488 KB Output is correct
5 Correct 125 ms 17488 KB Output is correct
6 Correct 126 ms 18256 KB Output is correct
7 Correct 123 ms 16976 KB Output is correct
8 Correct 127 ms 17860 KB Output is correct
9 Correct 126 ms 18260 KB Output is correct
10 Correct 128 ms 18768 KB Output is correct
11 Correct 156 ms 30556 KB Output is correct
12 Correct 167 ms 33148 KB Output is correct
13 Correct 165 ms 32240 KB Output is correct
14 Correct 171 ms 33020 KB Output is correct
15 Correct 165 ms 34396 KB Output is correct
16 Correct 130 ms 21088 KB Output is correct
17 Correct 132 ms 21968 KB Output is correct
18 Correct 139 ms 22868 KB Output is correct
19 Correct 126 ms 20264 KB Output is correct
20 Correct 123 ms 18772 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 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 2512 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 2396 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 2512 KB Output isn't correct
6 Halted 0 ms 0 KB -