fork download
copy 
  1. #include<bits/stdc++.h>
  2. typedef long long int lli;
  3. typedef long double ld;
  4. using namespace std;
  5. lli n,k,m;
  6. ld dp[23][52][23][102];//idx,index,cnt,money
  7. lli cost[55];
  8. ld benefit[55];
  9. lli vis[23][52][23][102];
  10. ld final_ans=0.0;
  11. lli mini_cost;
  12. lli dp1[23][52][23][102];
  13.  
  14.  
  15. ld solve(lli idx,lli index,lli cnt,lli money)
  16. {
  17.     if(money>m)
  18.     {
  19.         return -1000000000.0;
  20.     }
  21.  
  22.     if(idx==k)
  23.     {
  24.         if(money<=m)
  25.         {
  26.             return dp[idx][index][cnt][money]=0.0;
  27.         }
  28.         else
  29.         {
  30.             return -1000000000.0;
  31.         }
  32.     }
  33.  
  34.     if(vis[idx][index][cnt][money]==1)
  35.     {
  36.         return dp[idx][index][cnt][money];
  37.     }
  38.  
  39.     vis[idx][index][cnt][money]=1;
  40.  
  41.     lli i;
  42.  
  43.     ld res=-1000000000.0;
  44.  
  45.     for(i=1;i<=n;i++)
  46.     {
  47.         if(i!=index)
  48.         {
  49.             res=max(res,benefit[i]+solve(idx+1,i,1,money+cost[i]));
  50.         }
  51.         else
  52.         {
  53.             if(cnt==1)
  54.             res=max(res,(benefit[i]*1.0)/2+solve(idx+1,i,cnt+1,money+cost[i]));
  55.             else
  56.             res=max(res,solve(idx+1,i,cnt+1,money+cost[i]));
  57.         }
  58.     }
  59.  
  60.     return dp[idx][index][cnt][money]=res;
  61. }
  62.  
  63.  
  64.  
  65. lli go(lli idx,lli index,lli cnt,lli money,ld profit)
  66. {
  67.     lli i;
  68.  
  69.     if(idx==k)
  70.     {
  71.         if(money<=m)
  72.         {
  73.             return dp1[idx][index][cnt][money]=money;
  74.         }
  75.     }
  76.  
  77.     lli res=INT_MAX,mnn=INT_MAX,idxx;
  78.  
  79.     for(i=1;i<=n;i++)
  80.     {
  81.         if(i!=index)
  82.         {
  83.             if(dp[idx+1][i][1][money+cost[i]]+profit+benefit[i]==final_ans)
  84.             {
  85.                 res=min(res,go(idx+1,i,1,money+cost[i],profit+benefit[i]));
  86.             }
  87.         }
  88.         else
  89.         {
  90.             if(cnt==1)
  91.             {
  92.                 if(dp[idx+1][i][1][money+cost[i]]+profit+(benefit[i]*1.0)/2==final_ans)
  93.                 {
  94.                     res=min(res,go(idx+1,i,cnt+1,money+cost[i],profit+(benefit[i]*1.0)/2));
  95.                 }
  96.             }
  97.             else
  98.             {
  99.                 if(dp[idx+1][i][1][money+cost[i]]+profit==final_ans)
  100.                 {
  101.                     res=min(res,go(idx+1,i,cnt+1,money+cost[i],profit));
  102.                 }
  103.             }
  104.         }
  105.     }
  106.  
  107.     return dp1[idx][index][cnt][money]=res;
  108. }
  109.  
  110.  
  111.  
  112.  
  113. void path(lli idx,lli index,lli cnt,lli money,ld profit)
  114. {
  115.     if(idx==k)
  116.     {
  117.         return ;
  118.  
  119.     }
  120.  
  121.     lli i;
  122.  
  123.     for(i=1;i<=n;i++)
  124.     {
  125.         if(i!=index)
  126.         {
  127.             if(dp[idx+1][i][1][money+cost[i]]+profit+benefit[i]==final_ans && dp1[idx+1][i][1][money+cost[i]]==mini_cost)
  128.             {
  129.                 cout<<i<<" ";
  130.                 path(idx+1,i,1,money+cost[i],profit+benefit[i]);
  131.                 break;
  132.             }
  133.         }
  134.         else
  135.         {
  136.             if(cnt==1)
  137.             {
  138.                 if(dp[idx+1][i][1][money+cost[i]]+profit+(benefit[i]*1.0)/2==final_ans && dp1[idx+1][i][1][money+cost[i]]==mini_cost)
  139.                 {
  140.                     cout<<i<<" ";
  141.                     path(idx+1,i,cnt+1,money+cost[i],profit+(benefit[i]*1.0)/2);
  142.                     break;
  143.                 }
  144.             }
  145.             else
  146.             {
  147.                 if(dp[idx+1][i][1][money+cost[i]]+profit==final_ans && dp1[idx+1][i][1][money+cost[i]]==mini_cost)
  148.                 {
  149.                     cout<<i<<" ";
  150.                     path(idx+1,i,cnt+1,money+cost[i],profit);
  151.                     break;
  152.                 }
  153.             }
  154.         }
  155.     }
  156.  
  157. }
  158.  
  159.  
  160.  
  161. int main()
  162. {
  163.     ios_base::sync_with_stdio(false);
  164.     cin.tie(NULL); cout.tie(NULL);
  165.  
  166.  
  167.     lli i,j,q,t,a,d,b,c,l,r,e,idx,ind,index,u,v,x,y,z,h,sz,sz1,sz2,mid,len,tot,prev,temp,curr,p;
  168.     lli res=0,res1=0,res2=0,ans=0,ans1=0,ans2=0,val=0,val1=0,val2=0,rem=0,diff=0,cnt=0,flag=0,fl=0,sum=0,maxi=INT_MIN,mini=INT_MAX,total=0;
  169.  
  170.     string str,str1,str2;
  171.     char ch,ch1,ch2;
  172.  
  173.     while(1)
  174.     {
  175.         cin>>k>>n>>m;
  176.  
  177.         if(k==n && n==m && m==0)
  178.             break;
  179.  
  180.  
  181.         for(i=1;i<=n;i++)
  182.         {
  183.             cin>>cost[i]>>benefit[i];
  184.         }
  185.  
  186.         memset(vis,0,sizeof(vis));
  187.  
  188.         final_ans=solve(0,0,0,0);
  189.  
  190.         if(final_ans<=0.0)
  191.         {
  192.             cout<<"0.0"<<"\n";
  193.             cout<<"\n";
  194.  
  195.             continue;
  196.         }
  197.  
  198.         mini_cost=go(0,0,0,0,0.0);
  199.  
  200.         cout<<fixed<<setprecision(1)<<final_ans<<"\n";
  201.  
  202.         path(0,0,0,0,0.0);
  203.  
  204.         cout<<"\n";
  205.         //cout<<"\n";
  206.     }
  207. }
  208.  
  209. /*
  210. 5 10 10
  211. 3 78
  212. 4 4
  213. 3 2
  214. 3 1
  215. 4 3
  216. 3 4
  217. 3 6
  218. 3 2
  219. 3 1
  220. 5 9
  221. 0 0 0
  222. */
  223.  
Success #stdin #stdout 0s 4572KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ozerNZ
language:
C++14 (gcc 8.3)
created:
3 years 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!