Submission #989367

#	Time	Username	Problem	Language	Result	Execution time	Memory
989367		muhammad	Feast (NOI19_feast)	C++17	0 / 100	1 ms	348 KiB

feast

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long ll;

// Function to check if the given max time is feasible
bool feasible(const vector<ll>& work, ll N, ll K, ll max_time) {
    ll cows_used = 0;
    for (ll w : work) {
        cows_used += (w + max_time - 1) / max_time;
        if (cows_used > K) {
            return false;
        }
    }
    return true;
}

// Main function to find the minimum possible maximum time
ll find_min_time(const vector<ll>& work, ll N, ll K) {
    ll left = 1, right = *max_element(work.begin(), work.end());
    while (left < right) {
        ll mid = (left + right) / 2;
        if (feasible(work, N, K, mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

// Function to calculate the distribution of cows
vector<ll> distribute_cows(const vector<ll>& work, ll N, ll K, ll max_time) {
    priority_queue<pair<double, pair<ll, ll>>> pq;
    for (ll i = 0; i < N; ++i) {
        ll cows = 1;
        double time_per_cow = static_cast<double>(work[i]) / cows;
        pq.push({-time_per_cow, {cows, i}});
    }

    ll remaining_cows = K - N;
    while (remaining_cows > 0) {
        auto top = pq.top();
        pq.pop();
        ll cows = top.second.first;
        ll i = top.second.second;
        cows++;
        double time_per_cow = static_cast<double>(work[i]) / cows;
        pq.push({-time_per_cow, {cows, i}});
        remaining_cows--;
    }

    vector<ll> cows_distribution(N);
    while (!pq.empty()) {
        auto top = pq.top();
        pq.pop();
        cows_distribution[top.second.second] = top.second.first;
    }

    return cows_distribution;
}

int main() {
    ll N = 30;
    ll K = 200;
    vector<ll> work = {
        500, 29, 217, 48, 6, 3, 5, 15, 256, 358, 57, 21, 67, 41, 303, 24, 17,
        12, 94, 9, 4, 10, 423, 111, 183, 131, 7, 155, 34, 79
    };

    ll min_time = find_min_time(work, N, K);
    vector<ll> cows_distribution = distribute_cows(work, N, K, min_time);

    for (ll cows : cows_distribution) {
        cout << cows << " ";
    }
    cout << endl;

    return 0;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 8
• Subtask 3: 0 / 18
• Subtask 4: 0 / 10
• Subtask 5: 0 / 11
• Subtask 6: 0 / 20
• Subtask 7: 0 / 29