fork download 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct node
  6. {
  7.  
  8.     int obj;
  9.     double pbw;
  10.  
  11.  
  12. };
  13.  
  14. bool comparepbw(node p1, node p2)
  15. {
  16.     if(p1.pbw > p2.pbw)
  17.         return true;
  18.     else return false;
  19. }
  20.  
  21.  
  22. int main()
  23. {
  24.     int n,m;
  25.     cin>>n>>m;
  26.     int profit[n];
  27.     int weight[n];
  28.  
  29.  
  30.     for(int i=0; i<n; i++)
  31.     {
  32.         cin>>profit[i];
  33.     }
  34.     for(int i=0; i<n; i++)
  35.     {
  36.         cin>>weight[i];
  37.     }
  38.  
  39.     node Pbw[n];
  40.  
  41.     for(int i=0; i<n; i++)
  42.     {
  43.         Pbw[i].obj=i;
  44.         Pbw[i].pbw=double(profit[i])/double(weight[i]);
  45.     }
  46.     sort(Pbw,Pbw+n,comparepbw);
  47.  
  48.     double x[n];
  49.     memset(x, 0, sizeof(x));
  50.  
  51.     double rw=double(m);
  52.     for(int i=0; i<n; i++)
  53.     {
  54.         if(rw>0)
  55.         {
  56.             if(rw>=weight[Pbw[i].obj] )
  57.             {
  58.                 rw= double(rw)-double(weight[Pbw[i].obj]);
  59.                 x[Pbw[i].obj]=1;
  60.             }
  61.             else
  62.             {
  63.                 x[Pbw[i].obj]=double(rw)/double(weight[Pbw[i].obj]);
  64.                 rw=0;
  65.             }
  66.         }
  67.     }
  68.     double maxpf=0;
  69.     for(int i=0; i<n; i++)
  70.     {
  71.         maxpf=maxpf+x[i]*double(profit[i]);
  72.     }
  73.     cout<<"Maximum Profit :"<<maxpf<<endl;
  74.  
  75.  
  76. }
  77.  
Time limit exceeded #stdin #stdout 5s 5544KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/rBhdOi
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!