fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. pair<int,int> findans(vector<pair<int,int>>& v,int i,int budget,int cost,vector<vector<pair<int,int>>>& dp,int value)
  5. {
  6.  
  7.     //cout<<"for i = "<<i<<" and cost = "<<cost<<" and value = "<<value<<endl;
  8.     if(i<0)
  9.     {
  10.         //cout<<"Returning"<<endl;
  11.         return make_pair(value,cost);
  12.     }
  13.     if(dp[i][cost].first!=-1)
  14.     {
  15.         //cout<<"Value is present as - "<<dp[i][cost].first<<endl;
  16.         return dp[i][cost];
  17.     }
  18.     if(cost+v[i].first<=budget)
  19.     {
  20.  
  21.         pair<int,int> x=findans(v,i-1,budget,cost+v[i].first,dp,value+v[i].second);
  22.         pair<int,int> y=findans(v,i-1,budget,cost,dp,value);
  23.  
  24.         if(x.first==y.first)
  25.         {
  26.             if(x.second<y.second)
  27.             return dp[i][cost]=x;
  28.             else
  29.             return dp[i][cost]=y;
  30.  
  31.         }
  32.         else
  33.         if(x.first>y.first)
  34.         return dp[i][cost]=x;
  35.         else
  36.         return dp[i][cost]=y;
  37.     }
  38.     else
  39.     {
  40.         return dp[i][cost]=findans(v,i-1,budget,cost,dp,value);
  41.     }
  42.  
  43. }
  44.  
  45.  
  46. int32_t main()
  47. {
  48.     ios_base::sync_with_stdio(false);
  49.     cin.tie(NULL);
  50.     int budget,n;
  51.     cin>>budget>>n;
  52.     while(budget!=0 && n!=0){
  53.     vector<pair<int,int>> v;
  54.     for(int i=0;i<n;i++)
  55.     {
  56.         int cost;
  57.         int enjoy;
  58.         cin>>cost>>enjoy;
  59.         v.push_back(make_pair(cost,enjoy));
  60.     }
  61.     //sort(v.begin(),v.end(),compare);
  62.     int cost=0;
  63.     int newcost=0;
  64.     vector<vector<pair<int,int>>> dp(101,vector<pair<int,int>>(501));
  65.     for(int i=0;i<=100;i++)
  66.     {
  67.         for(int j=0;j<=500;j++)
  68.         {
  69.             dp[i][j].first=-1;
  70.         }
  71.     }
  72.     pair<int,int> ans=findans(v,n-1,budget,cost,dp,0);
  73.     cout<<ans.second<<" "<<ans.first<<endl;
  74.     //cout<<dp[9][0].first<<endl;
  75.     cin>>budget>>n;
  76.     }
  77. }
Time limit exceeded #stdin #stdout 5s 4197600KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/5e2C5G
language:
C++14 (gcc 8.3)
created:
3 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!