USACO 2015 December Contest Bronze Division - Contaminated Milk

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

This problem can be solved using brute force because the sum of all lengths is at most 100.

As an alternative, we can rely on doing some sort of sweeping through the queries to assess whenever the speed limit was broken but this is beyond what we need for this problem.

Source codes

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

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

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

    int n, m, d, s;
    cin >> n >> m >> d >> s;

    vector<vector<int> > earliest(m+1, vector<int> (n+1, 100000000));
    vector<int> sick(n+1, 100000000);
    for(int i = 1; i <= d; i++)
    {
        int p, m, t;
        cin >> p >> m >> t;
        earliest[m][p] = min(earliest[m][p], t);
    }

    for(int i = 1; i <= s; i++)
    {
        int p, t;
        cin >> p >> t;
        sick[p] = t;
    }

    int maxi = 0;
    for(int milktypes = 1; milktypes <= m; milktypes++)
    {
        bool ok = 1;
        for(int i = 1; i <= n; i++)
            if(sick[i] != 100000000)
            {
                if(earliest[milktypes][i] >= sick[i])
                    ok = 0;
            }
        int cnt = 0;
        for(int i = 1; i <= n; i++)
            if(earliest[milktypes][i] != 100000000)
                cnt++;
        if(ok)
            maxi = max(maxi, cnt);
    }
    cout << maxi;
    return 0;
}

INF = 100000000
with open("badmilk.in", "r") as fin:
    n, m, d, s = map(int, fin.readline().split())
    earliest = [[INF] * (n + 1) for _ in range(m + 1)]
    sick = [INF] * (n + 1)
    for _ in range(d):
        p, milk, t = map(int, fin.readline().split())
        earliest[milk][p] = min(earliest[milk][p], t)
    for _ in range(s):
        p, t = map(int, fin.readline().split())
        sick[p] = t
    maxi = 0
    for milktype in range(1, m + 1):
        ok = True
        for i in range(1, n + 1):
            if sick[i] != INF:
                if earliest[milktype][i] >= sick[i]:
                    ok = False
                    break
        cnt = 0
        for i in range(1, n + 1):
            if earliest[milktype][i] != INF:
                cnt += 1
        if ok:
            maxi = max(maxi, cnt)
with open("badmilk.out", "w") as fout:
    fout.write(str(maxi))