CUBE-T120: COI Coin Change

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

const int C = 10;
const int M = 1e6;

int dp[M + 1], par[M + 1], coin[C + 1], cnt[C + 1];

int main(){

    int price, mxPaid, nCoin;
    scanf("%d%d%d", &price, &mxPaid, &nCoin);
    for(int i = 1; i <= nCoin; ++i){
        scanf("%d", &coin[i]);
    }

    dp[0] = 0;
    for(int p = 1; p <= mxPaid; ++p){
        int mn = 1e9;
        for(int i = 1; i <= nCoin; ++i){
            if(p >= coin[i] && dp[p - coin[i]] < mn){
                mn = dp[p - coin[i]];
                par[p] = i;
            }
        }
        dp[p] = mn + 1;
    }

    int mnCoin = 1e9;
    int pCustomer = price;
    for(int p = price; p <= mxPaid; ++p){
        int coinCnt = dp[p] + dp[p - price];
        if(coinCnt < mnCoin){
            mnCoin = coinCnt;
            pCustomer = p;
        }
    }
    cout << dp[pCustomer] << ' ' << dp[pCustomer - price] << '\n';

    // Customer Coin Types
    int curr = pCustomer;
    while(curr != 0){
        ++cnt[par[curr]];
        curr -= coin[par[curr]];
    }
    for(int i = 1; i <= nCoin; ++i){
        cout << cnt[i] << ' ';
        cnt[i] = 0;
    }
    cout << '\n';

    // Seller Coin Types
    curr = pCustomer - price;
    while(curr != 0){
        ++cnt[par[curr]];
        curr -= coin[par[curr]];
    }
    for(int i = 1; i <= nCoin; ++i){
        cout << cnt[i] << ' ';
    }

    return 0;
}