USACO 2023 February Contest Bronze Division - Hungry Cow

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Given that the input data is already sorted, we only have two cases to deal with.

If at any point, we get the count become greater or equal to \(t\), we will print the current answer which is a running sum of minimums according to the formulas from the statement.

Source codes

The source codes in C++ and Python can be seen below.

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long n, t;
    cin >> n >> t;

    vector<pair<long long, long long> > cntt(n+1);
    for(int i = 1; i <= n; i++)
        cin >> cntt[i].first >> cntt[i].second;

    long long ans = 0, rem = 0;
    for(int i = 1; i <= n; i++)
    {
        ans += min(rem, min(t, cntt[i].first) - cntt[i-1].first - 1);
        rem -= min(rem, min(t, cntt[i].first) - cntt[i-1].first - 1);
        if(cntt[i].first > t)
        {
            cout << ans;
            return 0;
        }
        rem += cntt[i].second;
        ans++; rem--;
        if(cntt[i].first == t)
        {
            cout << ans;
            return 0;
        }
    } 
    if(cntt[n].first < t)
        ans += min(rem, t - cntt[n].first);
    cout << ans;
    return 0;
}

n, t = map(int, input().split())
cntt = [(0, 0)]
for _ in range(n):
    a, b = map(int, input().split())
    cntt.append((a, b))
ans = 0
rem = 0
printed = 0
for i in range(1, n + 1):
    temp = min(t, cntt[i][0]) - cntt[i - 1][0] - 1
    use = min(rem, temp)
    ans += use
    rem -= use
    if cntt[i][0] > t:
        print(ans)
        printed = 1
        break
    rem += cntt[i][1]
    ans += 1
    rem -= 1
    if cntt[i][0] == t:
        print(ans)
        printed = 1
        break
if printed == 0:
    if cntt[n][0] < t:
        ans += min(rem, t - cntt[n][0])
    print(ans)