fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. #define mp make_pair
  3. #define pb push_back
  4. #define vi vector<int>
  5. #define pii pair<int,int>
  6. #define vii vector<pii>
  7. #define rep(i,n) for(int i = 0; i < n; i++)
  8. #define rp(i,a,n) for(int i=a;i<=int(n);i++)
  9. #define IT(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
  10. #define all(x) (x).begin(), (x).end()
  11. #define ll unsigned long long int
  12. #define oo INT_MAX
  13. #define fill(a,b) memset(a,b,sizeof a)
  14. #define F first
  15. #define S second
  16. #define mod 1000000007
  17. using namespace std;
  18. int a[20],s,n,dp[12][2005][12];
  19. int f(int i,int sum,int cnt,int mn)
  20. {
  21.     if(i==n) {if(sum>=s)return cnt;else return 0;}
  22.     if(dp[i][sum][cnt]!=-1) return dp[i][sum][cnt];
  23.     int ans=0;
  24.     ans=max(ans,f(i+1,sum,cnt,mn));
  25.     if(sum+a[i]-mn<s) ans=max(ans,f(i+1,sum+a[i],cnt+1,min(mn,a[i])));
  26.     return dp[i][sum][cnt]=ans;
  27. }
  28. int main()
  29. {
  30.     int t;
  31.     cin >> t ;
  32.     rep(kk,t)
  33.     {
  34.         cin >> n >> s;
  35.         rep(i,n) scanf("%d",a+i);
  36.         fill(dp,-1);
  37.         cout << f(0,0,0,1000) << endl ;
  38.     }
  39. }
  40.  
Success #stdin #stdout 0s 3856KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Ltcf8H
language:
C++ 4.3.2 (gcc-4.3.2)
created:
8 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!