fork download
copy 
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3. int w[1000];
  4. int c[1000];
  5. vector<int> v[1000];
  6. int dp[20000][200];
  7. int main()
  8. {    
  9.     #ifndef ONLINE_JUDGE
  10.     freopen("input.txt","r",stdin);
  11.     freopen("output.txt","w",stdout);
  12.     #endif
  13.     ios::sync_with_stdio(false);
  14.     cin.tie(NULL);
  15.     int t;
  16.     cin>>t;
  17.     while(t--)
  18.     {
  19.         memset (dp,false,sizeof dp);
  20.         for(int i=0;i<1000;i++)
  21.         {
  22.             v[i].clear();
  23.         }
  24.         int n,m,x;
  25.         cin>>n>>m>>x;
  26.         for(int i=0;i<n;i++)
  27.         {
  28.             cin>>w[i];
  29.         }
  30.         for(int i=0;i<n;i++)
  31.         {
  32.             cin>>c[i];
  33.             v[c[i]].push_back(w[i]);
  34.         }
  35.         for(int i=0;i<v[1].size();i++)
  36.         {
  37.             dp[v[1][i]][1]=v[1][i];
  38.         }
  39.         for(int i=0;i<=x;i++)
  40.         {
  41.             for(int j=2;j<=m;j++)
  42.             {
  43.                 for(int k=0;k<v[j].size();k++)
  44.                 {   
  45.                     if(i-v[j][k]>=0)
  46.                     {
  47.                         if(dp[i-v[j][k]][j-1]>0)
  48.                         {
  49.                             dp[i][j]=dp[i-v[j][k]][j-1]+v[j][k];
  50.                         }
  51.                     }
  52.                 }
  53.             }
  54.         }
  55.         int ans=-1;
  56.         for(int i=0;i<=x;i++)
  57.         {
  58.             ans=max(ans,dp[i][m]);
  59.         }
  60.         if(ans==0)
  61.         {
  62.             cout<<-1<<endl;
  63.         }
  64.         else
  65.         {
  66.             cout<<x-ans<<endl;
  67.         }
  68.     }
  69.     return 0;
  70. }
Runtime error #stdin #stdout 0s 31024KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/T7GrNn
language:
C++14 (gcc 8.3)
created:
6 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!