fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAXN = 6;
  5. const int MAXR = 501;
  6. const int MAXS = 4100000;
  7.  
  8. long long n, t, r, d, e;
  9. long long c[MAXN];
  10. long long p[MAXR][MAXN];
  11. long long w[MAXN];
  12. long long s;
  13.  
  14. long long dp[MAXS];
  15. long long dp2[MAXS];
  16. long long b[MAXN];
  17.  
  18. int sti(long long m[])
  19. {
  20.     int idx = 0;
  21.     for (int i = 0; i < n; ++i)
  22.     {
  23.         idx += m[i] * w[i];
  24.     }
  25.     return idx;
  26. }
  27.  
  28. void its(int idx, long long m[])
  29. {
  30.     for (int i = 0; i < n; ++i)
  31.     {
  32.         m[i] = idx / w[i];
  33.         idx %= w[i];
  34.     }
  35. }
  36.  
  37. void buy(int item, long long cost, long long mc, int k)
  38. {
  39.     if (item == n)
  40.     {
  41.         int idx = sti(b);
  42.         dp2[idx] = mc - cost;
  43.         return;
  44.     }
  45.  
  46.     for (int q = 0; q <= c[item]; ++q)
  47.     {
  48.         long long new_cost = cost + q * (p[k][item] + d);
  49.         if (new_cost <= mc)
  50.         {
  51.             b[item] = q;
  52.             buy(item + 1, new_cost, mc, k);
  53.         }
  54.         else
  55.         {
  56.             break;
  57.         }
  58.     }
  59. }
  60.  
  61. int main()
  62. {
  63.     ios_base::sync_with_stdio(0);
  64.     cin.tie(0);
  65.     cout.tie(0);
  66.     if(fopen("busgame.inp","r"))
  67.     {
  68.         freopen("busgame.inp","r",stdin);
  69.         freopen("busgame.out","w",stdout);
  70.     }
  71.  
  72.     cin >> n >> t >> r >> d >> e;
  73.  
  74.     s = 1;
  75.     for (int i = 0; i < n; ++i)
  76.     {
  77.         cin >> c[i];
  78.         s *= (c[i] + 1);
  79.     }
  80.  
  81.     for (int i = 0; i < r; ++i)
  82.     {
  83.         for (int j = 0; j < n; ++j)
  84.         {
  85.             cin >> p[i][j];
  86.         }
  87.     }
  88.  
  89.     w[n - 1] = 1;
  90.     for (int i = n - 2; i >= 0; --i)
  91.     {
  92.         w[i] = w[i + 1] * (c[i + 1] + 1);
  93.     }
  94.  
  95.     for (int i = 0; i < s; ++i)
  96.     {
  97.         dp[i] = -1;
  98.     }
  99.  
  100.     vector<int> ngat;
  101.     ngat.push_back(0);
  102.     dp[0] = t;
  103.  
  104.     for (int k = 0; k < r; ++k)
  105.     {
  106.         long long mc = -1;
  107.         long long m[MAXN];
  108.         for (int idx : ngat)
  109.         {
  110.             its(idx, m);
  111.             long long cc = dp[idx];
  112.             for (int j = 0; j < n; ++j)
  113.             {
  114.                 cc += m[j] * (p[k][j] - e);
  115.             }
  116.             if (cc > mc)
  117.             {
  118.                 mc = cc;
  119.             }
  120.         }
  121.  
  122.         if (mc == -1)
  123.         {
  124.             break;
  125.         }
  126.  
  127.         for (int i = 0; i < s; ++i)
  128.         {
  129.             dp2[i] = -1;
  130.         }
  131.  
  132.         buy(0, 0, mc, k);
  133.  
  134.         ngat.clear();
  135.         for(int i = 0; i < s; ++i)
  136.         {
  137.             dp[i] = dp2[i];
  138.             if(dp[i] != -1)
  139.             {
  140.                 ngat.push_back(i);
  141.             }
  142.         }
  143.         if(ngat.empty())
  144.         {
  145.             break;
  146.         }
  147.     }
  148.  
  149.     long long ans = 0;
  150.     for (int i = 0; i < s; ++i)
  151.     {
  152.         if (dp[i] > ans)
  153.         {
  154.             ans = dp[i];
  155.         }
  156.     }
  157.     cout << ans << endl;
  158.  
  159.     return 0 ;
  160. }
  161.  
Success #stdin #stdout 0s 5704KB
comments (?)
stdin 
Standard input is empty
stdout 
0
https://ideone.com/GpwMzb
language:
C++14 (gcc 8.3)
created:
4 days 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!