1 条题解
-
0

#include <bits/stdc++.h> #define EB emplace_back typedef long long ll; typedef std::pair <int, int> pr; typedef std::vector <pr> vector; const int N = 5054, L = 2000054; struct monster { int h, a, d; monster * read() {return scanf("%d%d%d", &h, &a, &d), this;} inline int kill(int attack) {return (h - 1) / (attack - d) + 1;} } a[N], b[N]; int n, CA, CD; ll fy[L]; vector adjs[L]; inline void up(int &x, const int y) {x < y ? x = y : 0;} int main() { int i, j, k, l, m, attack, defense = 0, inf = 0, sup = 0, best_attack = 0, best_defense = 0; ll ans = LLONG_MAX, delta = 0, health = 0, current, best_health = 0; scanf("%d%d%d", &n, &CA, &CD); for (i = 0; i < n; ++i) up(inf, a[i].read()->d), up(sup, a[i].h + a[i].d), up(defense, a[i].a); for (++inf, i = 0; i < n; ++i) { fy[a[i].a] += a[i].kill(inf), m = a[i].h - 1; for (j = inf, l = -1; ; l = k, j = m / k + a[i].d + 1) { k = m / (j - a[i].d); if (~l) adjs[j].EB(a[i].a, k - l); if (!k) break; } } for (attack = inf; attack <= sup; ++attack) { for (const pr &adj : adjs[attack]) if (fy[adj.first] += adj.second, defense < adj.first) delta += adj.second, health += (adj.first - defense) * adj.second; for (; defense > 1; health += delta += fy[defense--]) if (delta + fy[defense] >= CD) break; current = health + (ll)CA * attack + (ll)CD * defense; if (current <= ans) ans = current, best_attack = attack, best_defense = defense, best_health = health; } printf("%lld %d %d\n", ++best_health, best_attack, best_defense); return 0; }
- 1
信息
- ID
- 5806
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者