USACO 2017 January Contest Silver Division - Cow Dance Show

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

This problem can be solved using a standard binary search on the answer and during one step of the algorithm, we can simulate the process using multiset and then if the ending time is at most \(t\), we found a potential answer, otherwise we need to search for a bigger answer.

Source code

The source code in C++ can be seen below.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ifstream cin("cowdance.in");
    ofstream cout("cowdance.out");

    int n, t;
    cin >> n >> t;
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    int L = 1;
    int R = n;
    int ans = 0;
    while (L <= R) {
        int mid = (L + R) / 2;
        multiset<int> s;
        for (int i = 0; i < mid; i++) {
            s.insert(v[i]);
        }
        for (int i = mid; i < n; i++) {
            int x = *s.begin();
            s.erase(s.lower_bound(x));
            s.insert(x + v[i]);
        }
        auto x = s.rbegin();
        if (*x <= t) {
            ans = mid;
            R = mid - 1;
        } 
        else {
            L = mid + 1;
        }
    }

    cout << ans;
    return 0;
}