Too Rich

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 395    Accepted Submission(s): 118

Problem Description
You are a rich person, and you think your wallet is too heavy and full now. So you want to give me some money by buying a lovely pusheen sticker which costs p dollars from me. To make your wallet lighter, you decide to pay exactly p dollars by as many coins and/or banknotes as possible.

For example, if p=17 and you have two $10 coins, four $5 coins, and eight $1 coins, you will pay it by two $5 coins and seven $1 coins. But this task is incredibly hard since you are too rich and the sticker is too expensive and pusheen is too lovely, please write a program to calculate the best solution.

Input
The first line contains an integer T indicating the total number of test cases. Each test case is a line with 11 integers p,c1,c5,c10,c20,c50,c100,c200,c500,c1000,c2000, specifying the price of the pusheen sticker, and the number of coins and banknotes in each denomination. The number ci means how many coins/banknotes in denominations of i dollars in your wallet.

1≤T≤20000
0≤p≤10⁹
0≤ci≤100000

Output
For each test case, please output the maximum number of coins and/or banknotes he can pay for exactly p dollars in a line. If you cannot pay for exactly p dollars, please simply output '-1'.

 #include <bits/stdc++.h>

 using namespace std;

 using LL = long long;

 const int maxn = ;

 const int val[] = {, , , , , , , , , , };

 int cnt[maxn],ret;

 LL sum[maxn];

 void dfs(LL rest,int pos,int cnt){

     if(rest < ) return;

     if(!pos){

         if(!rest) ret = max(ret,cnt);

         return;

     }

     LL tmp = max(0LL,rest - sum[pos-]);

     int tnt = tmp/val[pos];

     if(tmp%val[pos]) ++tnt;

     if(tnt <= ::cnt[pos]) dfs(rest - (LL)tnt*val[pos],pos - ,cnt + tnt);

     if(++tnt <= ::cnt[pos]) dfs(rest - (LL)tnt*val[pos],pos - ,cnt + tnt);

 }

 int main(){

     int kase,money;

     scanf("%d",&kase);

     while(kase--){

         scanf("%d",&money);

         for(int i = ; i < maxn; ++i){

             scanf("%d",cnt + i);

             sum[i] = sum[i - ] + static_cast<LL>(cnt[i])*val[i];

         }

         ret = -;

         dfs(money,,);

         printf("%d\n",ret);

     }

     return ;

 }