Competitive-Programming/CSES_DP2.cpp at master · sammyj11/Competitive-Programming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <bits/stdc++.h>


using namespace std;

#define ar array
#define ll long long
#define ld long double
#define sza(x) ((int)x.size())
#define all(a) (a).begin(), (a).end()

const int MAX_N = 1e5 + 5;
const ll MOD = 1e9 + 7;
const ll INF = 1e9;
const ld EPS = 1e-9;

int solve( long int x[], int coins,ll int dmon)
{


    int solver[coins+1][dmon+1];
    for (int i =0; i<= dmon; i++ )
    {
        solver[0][i] = 1;
    }

    for (int i =1; i<= coins; i++ )
    {
        solver[i][0] = 0;
    }

    for (int i =1; i<= coins; i++ )
{
        for(int j =1; j <= dmon; j++)
        {

            if((i == 1) && (j % x[0] == 0))
            {
                solver[i][j]= j/ x[0];
                //cout << solver[i][j] << endl;

            }
            else if((i == 1) && (j % x[0] != 0))
            {
                    solver[i][j] = -1;

            }
            else if(solver[i-1][j] == -1 && j %x[i-1] == 0)
            {
                solver[i][j]= j/ x[i-1];


            }
            else if(solver[i-1][j] == -1 && j % x[i-1] != 0)
            {
                solver[i][j] = -1;


            }

            else
            {
                if(j >= x[i-1] && solver[i][j-x[i-1]] != -1)
                {

                    solver[i][j] = min(solver[i-1][j], solver[i][j- x[i-1]]+1);

                }
                else {

                    solver[i][j] = solver[i-1][j];

                }
            }

        }
    }

if(solver[coins][dmon] != 0 && solver[coins][dmon] != -1)
{
cout << solver[coins][dmon];
}
else{
    cout << -1 << endl;
}
return solver[coins][dmon];


}

int main() {


     int numC;
     ll int numA;
     int ans;
     cin >> numC;
     cin >> numA;
    long int temp[numC];
     for(int i =0; i < numC; i++)
     {
         cin >> temp[i];
     }
    sort(temp, temp + numC);

     ans =  solve(temp, numC, numA);

        // cout << "Case #" << t << ": ";


}