fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ll long long
  6. #define debug(x) cout<<":["<<x<<"XE]"<<endl;
  7. #define debug2(x,y) cout<<":["<<x<<" "<<y<<"XE]"<<endl;
  8. #define _ ios_base::sync_with_stdio(false);
  9. #define mod 1000000007
  10.  
  11. ll n,x,dp[1000005][105],a[105];
  12.  
  13. int main()
  14. {_
  15.     ll t=1,ca=1;
  16.     //cin>>t;
  17.     while(t--){///problem: https://c...content-available-to-author-only...s.fi/problemset/task/1633
  18.         cin>>n>>x;
  19.         //memset(dp,INT_MAX,sizeof dp);
  20.         for(int i=0;i<=x;i++){
  21.             for(int j=0;j<=n;j++){
  22.                 dp[i][j]=1e9;
  23.             }
  24.         }
  25.         for(int i=1;i<=n;i++){
  26.             cin>>a[i];
  27.             dp[0][i]=0;
  28.         }dp[0][0]=0;
  29.         for(int i=1;i<=x;i++){
  30.             for(int j=1;j<=n;j++){
  31.                 dp[i][j]=dp[i][j-1];
  32.                 if(i-a[j]>=0)dp[i][j]=min(dp[i][j],dp[i-a[j]][j]+1);
  33.                 //debug(dp[i][j])
  34.             }
  35.         }
  36.         //debug(dp[1][2])
  37.         if(dp[x][n]!=1e9)cout<<dp[x][n];
  38.         else cout<<-1;
  39.     }
  40. }
  41.  
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/6bgQHD
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!