Submission #1196877

#TimeUsernameProblemLanguageResultExecution timeMemory
1196877LucaLucaMCloud Computing (CEOI18_clo)C++20
100 / 100
171 ms1352 KiB
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using ll = long long;
#define debug(x) #x << " = " << x << '\n'

const int NMAX = 2000;
const int CMAX = 50;
const ll INF = 1e18;

ll dp[NMAX * CMAX + 1];

struct Event {
  int type, c, f, v;
  bool operator < (const Event &other) const {
    return f != other.f? other.f < f : type < other.type;
  }
};

int main() {
  #ifdef LOCAL
    freopen("input.txt", "r", stdin);
  #endif
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);

  std::vector<Event> events;

  int n;
  std::cin >> n;

  for (int i = 0; i < n; i++) {
    int c, f, v;
    std::cin >> c >> f >> v;
    events.push_back({0, c, f, v});
  }
  
  int m;
  std::cin >> m;

  for (int i = 0; i < m; i++) {
    int c, f, v;
    std::cin >> c >> f >> v;
    events.push_back({1, c, f, v});
  }
  
  std::sort(events.begin(), events.end());

  for (int i = 1; i <= n * CMAX; i++) {
    dp[i] = -INF;
  }
  dp[0] = 0;

  int maxCores = 0;

  for (const auto &[type, c, f, v] : events) {
    if (type == 0) { // computer
      // 1. aleg sa il iau
      maxCores += c;
      for (int i = maxCores; i >= c; i--) {
        dp[i] = std::max(dp[i], dp[i - c] - v);
      }
    } else { // customer
      for (int i = 0; i + c <= maxCores; i++) {
        dp[i] = std::max(dp[i], dp[i + c] + v);
      }
    }
  }

  std::cout << *std::max_element(dp, dp + maxCores + 1);

  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...