Submission #1197443

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197443		alterio	Taxis (POI13_tak)	C++20	100 / 100	82 ms	4168 KiB

tak

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define ll long long
#define all(x) (x).begin(), (x).end()

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll m, d, n;
    cin >> m >> d >> n;
    vector<ll> v(n);
    for (int i = 0; i < n; i++) cin >> v[i];
    sort(all(v));
    int pos = lower_bound(all(v), m - d) - v.begin();
    if (pos == n) {
        cout << 0;
        return 0;
    }
    swap(v[pos], v.back());
    ll last = v.back();
    ll goal = d - (last - m + d) / 2;
    v.pop_back();
    sort(all(v));
    reverse(all(v));
    n--;
    ll cur = 0, ans = 1;
    for (int i = 0; i < n; i++) {
        if (cur >= goal) break;
        ll dist = abs(cur - d);
        v[i] -= dist;
        if (v[i] <= 0) break;
        cur += v[i];
        ans++;
    }
    cout << (cur < goal ? 0 : ans - (cur >= m));
}

• 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