Участник:Nik7/Rent your airplane and make money

Материал из DISCOPAL
< Участник:Nik7
Версия от 19:16, 22 ноября 2020; Nik7 (обсуждение | вклад) (Новая страница: «{{spojcode|RENT|Rent your airplane and make money|}} <code-cpp> // C++14 (gcc 8.3) #include <algorithm> #include <cstdint> #include <iostream> #include <vector>…»)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

«Rent your airplane and make money»

// C++14 (gcc 8.3)
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <vector>
 
struct Order {
  std::uint64_t start_time;
  std::uint64_t end_time;
  std::uint32_t price;
  Order() = default;
 
  friend std::istream& operator>>(std::istream& is, Order& order) {
    is >> order.start_time >> order.end_time >> order.price;
    order.end_time += order.start_time;
    return is;
  }
 
  bool operator<(const Order& rhs) const {
    return end_time < rhs.end_time;
  }
};
 
int main() {
  int T, n;
  std::cin >> T;
  for (auto t = 0; t < T; ++t) {
    std::cin >> n;
    auto orders = std::vector<Order>(n);
    auto gains = std::vector<std::uint64_t>(n);
 
    for (auto& order : orders) {
      std::cin >> order;
    }
    std::sort(orders.begin(), orders.end());
    for (auto i = 0lu; i < orders.size(); ++i) {
      gains[i] = orders[i].price;
    }
    for (auto i = 1lu; i < orders.size(); ++i) {
      for (auto j = 0lu; j < i; ++j) {
        if (orders[i].start_time >= orders[j].end_time) {
          if (gains[j] + orders[i].price > gains[i]) {
            gains[i] = gains[j] + orders[i].price;
          }
        }
      }
    }
    std::cout << *std::max_element(gains.begin(), gains.end()) << std::endl;
  }
  return 0;
}