fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long int
  4. #define rep(i,a,b) for(ll i=a;i<b;i++)
  5. #define vi vector<ll>
  6. #define pii pair<int,int>
  7. #define vii vector< pair<int,int> >
  8. #define pb push_back
  9.  
  10. using namespace std;
  11.  
  12. int dp[101][101];
  13.  
  14. int helper(vector <pii> &a,int st,int col,int W,int m){
  15.     if(W<0)
  16.         return -10000000;
  17.     if(st>=a.size()){
  18.         if(col==m+1)
  19.             return 0;
  20.         else
  21.             return -10000000;
  22.     }
  23.     if(a[st].first!=col)
  24.         return dp[st][W]=helper(a,st+1,col,W,m);
  25.     if(dp[st][W]!=-1)
  26.         return dp[st][W];
  27.     int ans=-1000000,ost=st;
  28.     while(st<a.size()&&a[st].first==col){
  29.         ans=max(ans,a[st].second+helper(a,st+1,col+1,W-a[st].second,m));
  30.         st++;
  31.     }
  32.     return dp[ost][W]=ans;
  33. }
  34.  
  35. void solve()
  36. {
  37.     ll n,m,W,p;
  38.     cin>>n>>m>>W;
  39.     vector <pii> vp;
  40.     rep(i,0,n){
  41.         cin>>p;
  42.         vp.pb({0,p});
  43.     }
  44.     rep(i,0,n){
  45.         cin>>p;
  46.         vp[i].first=p;
  47.     }
  48.     sort(begin(vp),end(vp));
  49.     memset(dp,-1,sizeof dp);
  50.     int ans=helper(vp,0,1,W,m);
  51.     if(ans<0)
  52.         ans=-1;
  53.     else
  54.         ans=W-ans;
  55.     cout<<ans<<"\n";
  56. }
  57.  
  58. int main()
  59. {
  60.     ios_base::sync_with_stdio(false);
  61.     cin.tie(NULL);
  62.     cout.tie(NULL);
  63.     ll t;
  64.     t=1;
  65.     cin>>t;
  66.     while(t--)
  67.         solve();
  68. }
  69.  
Success #stdin #stdout 0s 4584KB
comments (?)
stdin
copy 
4
9 3 10
2 3 4 2 3 4 2 3 4
1 1 1 2 2 2 3 3 3
9 3 10
1 3 5 1 3 5 1 3 5
1 1 1 2 2 2 3 3 3
3 3 10
3 4 4
1 2 3
3 3 10
3 3 3
1 2 1
stdout
copy 
0
1
-1
-1
https://ideone.com/2dWmnw
language:
C++14 (gcc 8.3)
created:
4 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!