1. C++ / Говнокод #29224

    0

    1. 01
    2. 02
    3. 03
    4. 04
    5. 05
    6. 06
    7. 07
    8. 08
    9. 09
    10. 10
    11. 11
    12. 12
    13. 13
    14. 14
    15. 15
    16. 16
    17. 17
    18. 18
    19. 19
    20. 20
    21. 21
    22. 22
    23. 23
    24. 24
    25. 25
    26. 26
    27. 27
    28. 28
    29. 29
    30. 30
    31. 31
    32. 32
    33. 33
    34. 34
    35. 35
    36. 36
    37. 37
    38. 38
    39. 39
    40. 40
    41. 41
    42. 42
    43. 43
    44. 44
    45. 45
    46. 46
    47. 47
    48. 48
    49. 49
    50. 50
    51. 51
    52. 52
    53. 53
    54. 54
    55. 55
    56. 56
    57. 57
    58. 58
    59. 59
    60. 60
    61. 61
    62. 62
    63. 63
    64. 64
    65. 65
    66. 66
    67. 67
    68. 68
    69. 69
    70. 70
    71. 71
    72. 72
    73. 73
    74. 74
    75. 75
    76. 76
    77. 77
    78. 78
    79. 79
    80. 80
    81. 81
    82. 82
    83. 83
    84. 84
    85. 85
    86. 86
    87. 87
    88. 88
    89. 89
    90. 90
    91. 91
    92. 92
    93. 93
    94. 94
    95. 95
    96. 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;
  }

    олимпиадное говно

    Запостил: letipetukh1, 26 Января 2026

    Комментарии (1) RSS

    • ava guest6 5 часов назад # 0

      >> vector<bool>

      самый смешной и неожиданный тип, наверное
      Ответить

    Добавить комментарий