[UVa] 10465 Homer Simpson.cpp

#include <cstdio>
#include <algorithm>
using namespace std;

int Time[10005];
int num[10005];

int Knapsack(int m, int t)
{
    for (int i = 0; i + m <= t; ++i)
        if (Time[i+m] < Time[i] + m) {
            Time[i+m] = Time[i] + m;
            num[i+m] = num[i] + 1;
        }
}
int main()
{
    int m, n, t;
    while (scanf("%d %d %d", &m, &n, &t) != EOF) {
        fill(Time, Time+t+1, 0);
        fill(num, num+t+1, 0);
        if (m > n) swap(m, n);

        Knapsack(m, t);
        Knapsack(n, t);

        if (Time[t] == t) printf("%d\n", num[t]);
        else printf("%d %d\n", num[Time[t]], t-Time[t]);
    }
}