fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5.  
  6. int n, T, R, d, e, C[6], P[505][6], W[6];
  7.  
  8. namespace Subtask12 {
  9.     void solve() {
  10.         W[0] = 1;
  11.         for (int i = 0; i < n; i++) W[i + 1] = W[i] * (C[i] + 1);
  12.         int S = W[n];
  13.         vector<ll> dp(S, -1);
  14.         dp[0] = T;
  15.         for (int r = 0; r < R; r++) {
  16.             for (int i = 0; i < n; i++) {
  17.                 ll gain = P[r][i] - e;
  18.                 if (gain <= 0) continue;
  19.                 for (int mask = S - 1; mask >= 0; mask--) {
  20.                     if (dp[mask] == -1) continue;
  21.                     int it = (mask / W[i]) % (C[i] + 1);
  22.                     if (it > 0) {
  23.                         int nmask = mask - W[i];
  24.                         dp[nmask] = max(dp[nmask], dp[mask] + gain);
  25.                     }
  26.                 }
  27.             }
  28.             for (int i = 0; i < n; i++) {
  29.                 ll cost = P[r][i] + d;
  30.                 for (int mask = 0; mask < S; mask++) {
  31.                     if (dp[mask] == -1) continue;
  32.                     int it = (mask / W[i]) % (C[i] + 1);
  33.                     if (it < C[i] && dp[mask] >= cost) {
  34.                         int nmask = mask + W[i];
  35.                         dp[nmask] = max(dp[nmask], dp[mask] - cost);
  36.                     }
  37.                 }
  38.             }
  39.         }
  40.         cout << dp[0] << '\n';   
  41.     }
  42. }
  43.  
  44. namespace Subtask3 {
  45.     bool check() {
  46.         return d == 0 && e == 0;
  47.     }
  48.     ll ans, best;
  49.     void dfs(int r, int i, ll cur, ll sum) {
  50.         if (i == n) {
  51.             best = max(best, cur + sum);
  52.             return;
  53.         }
  54.         if (P[r + 1][i] <= P[r][i]) {
  55.             dfs(r, i + 1, cur, sum);
  56.             return;
  57.         }
  58.         int xmax = min(C[i], (int)(cur / P[r][i]));
  59.         for (int x = xmax; x >= 0; x--) {
  60.             ll cost = x * P[r][i], gain = x * P[r + 1][i];
  61.             dfs(r, i + 1, cur - cost, sum + gain);
  62.         }
  63.     }
  64.     void solve() {
  65.         ans = T;
  66.         for (int r = 0; r < R - 1; r++) {
  67.             ll cost = 0, gain = 0;
  68.             for (int i = 0; i < n; i++) 
  69.                 if (P[r + 1][i] > P[r][i]) {
  70.                     cost += C[i] * P[r][i];
  71.                     gain += C[i] * P[r + 1][i];
  72.                 }
  73.             if (ans >= cost) ans = ans - cost + gain;
  74.             else {
  75.                 best = ans;
  76.                 dfs(r, 0, ans, 0);
  77.                 ans = best;
  78.             }
  79.         }
  80.         cout << ans << '\n';
  81.     }
  82. }
  83.  
  84. void solve() {
  85.     cin >> n >> T >> R >> d >> e;
  86.     for (int i = 0; i < n; i++) cin >> C[i];
  87.     for (int r = 0; r < R; r++)
  88.         for (int i = 0; i < n; i++)
  89.             cin >> P[r][i];
  90.     if (Subtask3::check()) Subtask3::solve();
  91.     else Subtask12::solve();
  92. }
  93.  
  94. int main() {
  95.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  96.  
  97.     #define TASK "BUSGAME"
  98.     if (fopen(TASK".INP", "r")) {
  99.         freopen(TASK".INP", "r", stdin);
  100.         freopen(TASK".OUT", "w", stdout);
  101.     }
  102.  
  103.     int tests = 1; // cin >> tests;
  104.     while (tests--) solve();
  105.  
  106.     #ifdef LOCAL
  107.     cerr << "\nTime elapsed: " << clock() << " ms.\n";
  108.     #endif
  109.     return 0;
  110. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
3 2 2 1 0
1 1 1
1 1 1
2 3 4
stdout
copy 
4
https://ideone.com/h92XUA
ĐTQG Cà Mau 2025 - Bài 3 - Trò chơi kinh doanh
language:
C++14 (gcc 8.3)
created:
6 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!