Solução OBI 2015

banco.cpp

// Ivan Carvalho
// O Banco Inteligente - Fase 1 Programação Nível 2 - OBI 2015
// O(n*S)
// n = n_2 + n_5 + n_10 + n_20 + n_50 + n_100
#include <bits/stdc++.h>
#define MAXS 5001
typedef long long ll;
ll modos[MAXS], temp[MAXS], qtd[10],n,vetor[10] = {2,5,10,20,50,100};
int main(){
	scanf("%lld",&n);
	for(int i=0;i<6;i++) scanf("%lld",&qtd[i]);
	modos[0] = 1;
	for(int i=0;i<6;i++){
		memset(temp,0,sizeof(temp));
		for(int j=1;j <= qtd[i];j++){
			for(int k = j * vetor[i]; k <= n; k++){
				temp[k] += modos[k - vetor[i]*j];
			}
		}
		for(int i=0;i<=n;i++) modos[i] += temp[i];
	}
	printf("%lld\n",modos[n]);
	return 0;
}