- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
cin >> N >> L >> T;
total = 0;
for (int i = 0; i < N; i++) {
cin >> S[i] >> H[i] >> P[i];
total += H[i] * P[i];
}
fix_order();
for (int ind = 0; ind < N; ind++) {
int len = ind + 1;
set<pair<long long, int>> events, comps;
vector<long long> sum_hp(len);
copy(H, H + len, sum_hp.begin());
sum_hp[ind] = 0;
vector<int> ord(len);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int i, int j) {
return S[i] < S[j];
});
comps.emplace(T, -1);
for (int i = 0; i < len; i++) {
int j = i + 1;
while (j < len && S[ord[i]] == S[ord[j]]) {
sum_hp[ord[i]] += sum_hp[ord[j]];
++j;
}
comps.emplace(S[ord[i]], ord[i]);
i = j - 1;
}
for (auto it = comps.begin(); next(it) != comps.end(); ++it) {
long long dist = next(it)->first - it->first;
int idx = it->second;
if (sum_hp[idx] > 0) {
events.emplace((dist + sum_hp[idx] - 1) / sum_hp[idx], idx);
}
}
vector<bool> visited(len);
vector<bool> added(len);
long long good_sum = 0, last_time = 0, govno = T, rakom_bokom = 0;
for (auto [spawn, i] : comps) {
if (spawn >= S[ind] && i != -1) {
good_sum += sum_hp[i];
added[i] = true;
}
}
auto Upd = [&](long long time) -> void {
long long F = govno - S[ind] - rakom_bokom;
if (F <= 0) {
return;
}
long long r1 = clamp(F / (H[ind] + good_sum) + 1, last_time, time);
long long r2 = good_sum == 0 ? time : clamp(F / good_sum + 1, last_time, time);
dp_diff_i[last_time] += H[ind] * P[ind];
dp_diff_i[r1] -= H[ind] * P[ind];
dp_diff[r1] += F * P[ind];
dp_diff[r2] -= F * P[ind];
dp_diff_i[r1] -= good_sum * P[ind];
dp_diff_i[r2] += good_sum * P[ind];
last_time = time;
};
vector<bool> skip(len), finished(len);
while (!events.empty()) {
auto [time, i] = *events.begin();
events.erase(events.begin());
if (time > L) {
break;
}
if (skip[i] || sum_hp[i] == 0) {
continue;
}
Upd(time);
auto it = comps.upper_bound({S[i], INT_MAX});
if (it->second == -1 || finished[it->second]) {
good_sum -= sum_hp[i];
finished[i] = true;
govno = S[i];
continue;
}
if (!added[i] && it->second + sum_hp[i] * time >= S[ind]) {
added[i] = true;
good_sum += sum_hp[i];
rakom_bokom += S[i] - S[ind];
}
sum_hp[i] += sum_hp[it->second];
skip[it->second] = true;
long long next_pos = next(it)->first;
comps.erase(it);
events.emplace(time + (next_pos - S[i] - sum_hp[i] * time + sum_hp[i] - 1) / sum_hp[i], i);
}
Upd(L + 1);
}
long long cur_diff = 0, cur_diff_i = 0;
for (int i = 0; i <= L; i++) {
cur_diff += dp_diff[i];
cur_diff_i += dp_diff_i[i];
dp[i] = cur_diff + cur_diff_i * i;
}
Follow us!