fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. struct Unit {
  8.     long long a;
  9.     long long b;
  10.     int c;
  11. };
  12.  
  13. struct EnemyType {
  14.     long long d;
  15.     long long e;
  16. };
  17.  
  18. struct State {
  19.     int killed;
  20.     long long damage;
  21.  
  22.     bool operator<(const State& other) const {
  23.         if (killed != other.killed) {
  24.             return killed < other.killed;
  25.         }
  26.         return damage < other.damage;
  27.     }
  28. };
  29.  
  30. int main() {
  31.     ios_base::sync_with_stdio(false);
  32.     cin.tie(NULL);
  33.  
  34.     int m, n, k, f;
  35.     if (!(cin >> m >> n >> k >> f)) return 0;
  36.  
  37.     vector<Unit> units(m);
  38.     for (int i = 0; i < m; ++i) {
  39.         cin >> units[i].a >> units[i].b >> units[i].c;
  40.     }
  41.  
  42.     vector<EnemyType> wave_pattern(n);
  43.     for (int i = 0; i < n; ++i) {
  44.         cin >> wave_pattern[i].d >> wave_pattern[i].e;
  45.     }
  46.  
  47.     long long total_enemies = (long long)n * f;
  48.  
  49.     vector<State> dp(k + 1, {-1, -1});
  50.     dp[0] = {0, 0};
  51.  
  52.     for (int c = 0; c <= k; ++c) {
  53.         if (dp[c].killed == -1) continue;
  54.  
  55.         if (dp[c].killed >= total_enemies) {
  56.             cout << c << endl;
  57.             return 0;
  58.         }
  59.  
  60.         for (const auto& unit : units) {
  61.             if (c + unit.c > k) continue;
  62.  
  63.             int curr_killed = dp[c].killed;
  64.             long long curr_dmg = dp[c].damage;
  65.             long long hero_hp = unit.b;
  66.  
  67.             while (curr_killed < total_enemies && hero_hp > 0) {
  68.                 const EnemyType& enemy_stats = wave_pattern[curr_killed % n];
  69.  
  70.                 long long enemy_hp = enemy_stats.e - curr_dmg;
  71.  
  72.                 long long turns_to_kill_enemy = (enemy_hp + unit.a - 1) / unit.a;
  73.                 long long turns_to_kill_hero = 1e18;
  74.                 if (enemy_stats.d > 0) {
  75.                     turns_to_kill_hero = (hero_hp + enemy_stats.d - 1) / enemy_stats.d;
  76.                 }
  77.  
  78.                 long long turns = min(turns_to_kill_enemy, turns_to_kill_hero);
  79.  
  80.                 long long dmg_dealt = turns * unit.a;
  81.                 long long dmg_taken = turns * enemy_stats.d;
  82.  
  83.                 curr_dmg += dmg_dealt;
  84.                 hero_hp -= dmg_taken;
  85.  
  86.                 bool enemy_dead = (curr_dmg >= enemy_stats.e);
  87.                 bool hero_dead = (hero_hp <= 0);
  88.  
  89.                 if (enemy_dead) {
  90.                     curr_killed++;
  91.                     curr_dmg = 0;
  92.                 }
  93.  
  94.                 if (hero_dead) {
  95.                     break;
  96.                 }
  97.             }
  98.  
  99.             int next_cost = c + unit.c;
  100.             State new_state = {curr_killed, curr_dmg};
  101.  
  102.             if (dp[next_cost] < new_state) {
  103.                 dp[next_cost] = new_state;
  104.             }
  105.         }
  106.     }
  107.  
  108.     for(int c = 0; c <= k; ++c) {
  109.         if(dp[c].killed >= total_enemies) {
  110.             cout << c << endl;
  111.             return 0;
  112.         }
  113.     }
  114.  
  115.     cout << "-1" << endl;
  116.     return 0;
  117. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
2 4 10 1
5 7 3
8 2 2
12 12
2 1
2 2
5 3
stdout
copy 
7
https://ideone.com/6xGT6d
language:
C++14 (gcc 8.3)
created:
5 hours 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!