fork(1) download 
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <algorithm>
  4. #include <cstring>
  5. #include <bitset>
  6. #include <vector>
  7.  
  8. #define MAXN 40000
  9.  
  10. using namespace std;
  11.  
  12.  
  13. struct dish
  14. {
  15.     string name;
  16.     long long s;
  17.     int p;
  18. };
  19.  
  20. long long n, m;
  21. long long s[MAXN]; 
  22. int cd[MAXN];
  23. int cdif[MAXN];
  24. bool* dif[MAXN];
  25. dish md[101];
  26.  
  27. void init()
  28. {
  29.     cin >> n >> m;
  30.     for (int i = 1; i <= n; i++)
  31.     {
  32.         double t;
  33.         cin >> md[i].name >> md[i].p >> t;
  34.         md[i].s = (long long)(t*1000);
  35.     }
  36.     for (int i = 0; i < MAXN; i++)
  37.         dif[i] = (bool*) malloc(101);
  38.     for (int i = 0; i < MAXN; i++)
  39.         for (int j = 0; j < 101; j++)
  40.             dif[i][j] = false;
  41. }
  42.  
  43. void initd()
  44. {
  45.     s[0] = 0;
  46.     m = m * 1000;
  47. }
  48.  
  49. void solve()
  50. {
  51.     for (int i = 0; i < MAXN; i++) s[i] = 10000000000000000LL;
  52.     initd();
  53.     for (int i = 0; i < MAXN; i++)
  54.     {
  55.         for (int j = 1; j <= n; j++)
  56.         {
  57.             if (i + md[j].s < MAXN && md[j].p + s[i] < s[i + md[j].s]) // prove price
  58.             {
  59.                      s[i + md[j].s] = md[j].p + s[i];
  60.  
  61.                      cdif[i + md[j].s] = cdif[i] + (dif[i][j] ? 0 : 1);
  62.                      cd[i + md[j].s] = j;
  63.  
  64.                      dif[i][j] = true;
  65.                      memcpy(dif[i + md[j].s],dif[i], 101);
  66.             }
  67.             if (i + md[j].s < MAXN && md[j].p + s[i] == s[i + md[j].s])
  68.             {
  69.                 if (cdif[i] + (dif[i][j] ? 0 : 1) > cdif[i + md[j].s]) // prove count diff and diff
  70.                 {
  71.                      s[i + md[j].s] = md[j].p + s[i];
  72.  
  73.                      cdif[i + md[j].s] = cdif[i] + (dif[i][j] ? 0 : 1);
  74.                      cd[i + md[j].s] = j;
  75.  
  76.                      dif[i][j] = true;
  77.                      memcpy(dif[i + md[j].s],dif[i], 101);
  78.                 }
  79.             }
  80.  
  81.         }
  82.     }
  83. }
  84.  
  85. void recoversolve()
  86. {
  87.     int cnt[101]; for (int i = 0; i < 101; i++) cnt[i] = 0;
  88.     long long int pr = 1000000000000000LL;
  89.     int u = 0;
  90.     int cntdif = 0;
  91.     for (int i = m; i < MAXN; i++)
  92.     {
  93.         if (s[i] < pr)
  94.         {
  95.             pr = s[i];
  96.             cntdif = cdif[i];
  97.             u = i;
  98.         }
  99.         if (s[i] == pr && cdif[i] > cntdif)
  100.         {
  101.             pr = s[i];
  102.             cntdif = cdif[i];
  103.             u = i;
  104.         }
  105.     }
  106.     cout << pr << endl;
  107.     while (pr > 0)
  108.     {
  109.         cnt[cd[u]]++;
  110.         pr -= md[cd[u]].p;
  111.         u -= md[cd[u]].s;
  112.     }
  113.  
  114.     for (int i = 1; i <= n; i++)
  115.     {
  116.         if (cnt[i] > 0)
  117.         {
  118.             cout << md[i].name << " " << cnt[i] << endl;
  119.         }
  120.     }
  121. }
  122. void end()
  123. {
  124.     for (int i = 0; i < MAXN; i++)
  125.         free(dif[i]);
  126. }
  127. int main()
  128. {
  129.     init();
  130.     solve();
  131.     recoversolve();
  132.     end();
  133.     return 0;
  134. }
  135.  
Success #stdin #stdout 0.01s 4216KB
comments (?)
stdin 
Standard input is empty
stdout 
0
https://ideone.com/5Lu9DH
language:
C++ (gcc 8.3)
created:
10 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!