oj.uz

Submission #122147

# Submission time Handle Problem Language Result Execution time Memory
122147 2019-06-27T17:26:52 Z popovicirobert Taxis (POI13_tak) C++14
100 / 100
 139 ms 4224 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define lsb(x) (x & (-x)) 

using namespace std;

const ll INF = 2e18;

int main() {
	//ifstream cin("A.in");
	//ofstream cout("A.out");
	int n, i; 
	ll m, d;
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	cin >> m >> d >> n;

	vector <ll> arr(n);
	for(i = 0; i < n; i++) {
		cin >> arr[i];
	}

	sort(arr.begin(), arr.end(), greater<ll>());

	ll mn = INF, id = -1;
	for(i = 0; i < n; i++) {
		if(mn > arr[i] && arr[i] >= m - d) {
			mn = arr[i];
			id = i;
		}
	}

	if(id == -1) {
		cout << 0;
		return 0;
	}

	int ans = 0;
	ll x = 0;
	for(i = 0; i < n && x < d; i++) {
		if(id == i) {
			continue;
		}
		if(arr[i] > d - x) {
			x += arr[i] - (d - x);
			ans++;
		}
	}

	if(x < d) {
		if(2LL * (d - x) + m - d <= mn) {
			ans++;
		}
		else {
			cout << 0;
			return 0;
		}
	}
	else if(x < m) {
		ans++;	
	}

	cout << ans;
	
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 380 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 428 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 768 KB Output is correct
2 Correct 4 ms 640 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 868 KB Output is correct
2 Correct 16 ms 896 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1408 KB Output is correct
2 Correct 56 ms 2048 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 2688 KB Output is correct
2 Correct 89 ms 2944 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 4224 KB Output is correct
2 Correct 114 ms 3456 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 4224 KB Output is correct
2 Correct 133 ms 4224 KB Output is correct