fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define dd double
  5. #define ld long double
  6. #define ull unsigned long long
  7. #define yes cout << "YES\n"
  8. #define no cout << "NO\n"
  9. #define el "\n"
  10. #define Arwa ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  11. #define fix(x) cout << fixed << setprecision(x)
  12. #define all(v) v.begin(),v.end()
  13. #define dpp(v,val) memset(v,val,sizeof(v))
  14. #define mod 1e9+7
  15. #define oo 1e18
  16. const int N = 1e5 + 5;
  17. int n,s,k;
  18. vector<int>v; 
  19. vector<char>c;
  20. int dp[55][55][2005];
  21. int solve(int i,int j,int eat) // index , last index 
  22. {
  23.   if(i==n+1)
  24.   {
  25.     if(eat>=k) return 0;
  26.     return oo;
  27.   }
  28.   int &ret=dp[i][j][eat];
  29.   if(ret!=-1) return ret;
  30.   int t=oo,l=oo;
  31.   if(j==0)
  32.   t=solve(i+1,i,eat+v[i])+1;
  33.   else
  34.   {
  35.     if(v[j]<v[i]&&c[j]!=c[i])
  36.     t=solve(i+1,i,eat+v[i])+1;
  37.   }
  38.   l=solve(i+1,j,eat)+1;
  39.   return ret=min(t,l);
  40. }
  41. void HereWeGoAgain()
  42. {
  43.    cin>>n>>s>>k;
  44.    v.resize(n+1);c.resize(n+1);
  45.    for(int i=1;i<=n;i++) cin>>v[i];
  46.    for(int i=1;i<=n;i++) cin>>c[i];
  47.    dpp(dp,-1);
  48.    int mn=oo;
  49.    for(int i=1;i<=n;i++)
  50.    mn=min(mn,solve(i,0,0));
  51.    if(mn==oo) cout<<-1<<el; else 
  52.    cout<<mn<<el;
  53. }
  54. int32_t main() 
  55. {
  56.     Arwa
  57.     int t=1;
  58.     //cin>>t;
  59.     for(int i=1;i<=t;i++)
  60.     {
  61.     HereWeGoAgain();
  62.     }
  63.     return 0;
  64. }
  65.  
Success #stdin #stdout 0.01s 50960KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/DH3hju
language:
C++ (gcc 8.3)
created:
3 days 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!