Submission #122147

#	Time	Username	Problem	Language	Result	Execution time	Memory
122147		popovicirobert	Taxis (POI13_tak)	C++14	100 / 100	139 ms	4224 KiB

tak

#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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10