Submission #679880

#	Time	Username	Problem	Language	Result	Execution time	Memory
679880		peijar	Cloud Computing (CEOI18_clo)	C++17	100 / 100	343 ms	2852 KiB

clo

#include <bits/stdc++.h>
#include <linux/limits.h>
#define int long long
using namespace std;

namespace std {
template <typename T> ostream &operator<<(ostream &out, const vector<T> &vec) {
  out << "[";
  for (int i = 0; i < (int)vec.size(); ++i) {
    out << vec[i];
    if (i + 1 < (int)vec.size())
      out << ", ";
  }
  return out << "]";
}
} // namespace std

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << H;
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

struct Ordinateur {
  int nbCoeurs, freq, prix;

  bool operator<(Ordinateur other) const { return freq > other.freq; }
};

const int INF = 1e18;

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int nbOrdinateurs;
  cin >> nbOrdinateurs;

  vector<Ordinateur> ordinateurs(nbOrdinateurs);
  for (auto &[nbCoeurs, freq, prix] : ordinateurs) {
    cin >> nbCoeurs >> freq >> prix;
  }

  int nbOrdres;
  cin >> nbOrdres;
  vector<Ordinateur> ordres(nbOrdres);
  for (auto &[nbCoeurs, freq, prix] : ordres)
    cin >> nbCoeurs >> freq >> prix;
  sort(ordinateurs.begin(), ordinateurs.end());
  sort(ordres.begin(), ordres.end());

  int totCoeurs = 0;
  for (auto [nbCoeurs, freq, prix] : ordinateurs)
    totCoeurs += nbCoeurs;
  vector<int> freqCoeur(totCoeurs), prixCoeur(totCoeurs);
  int curOrdi = 0;
  vector<int> dp(totCoeurs + 1, -INF);
  dp[0] = 0;
  for (auto [coeurOrdre, freqOrdre, gainOrdre] : ordres) {
    while (curOrdi < nbOrdinateurs and ordinateurs[curOrdi].freq >= freqOrdre) {
      int coeurs = ordinateurs[curOrdi].nbCoeurs;
      int prix = ordinateurs[curOrdi++].prix;
      for (int c = totCoeurs; c >= coeurs; --c)
        dp[c] = max(dp[c], dp[c - coeurs] - prix);
    }

    for (int c = 0; c + coeurOrdre <= totCoeurs; ++c)
      dp[c] = max(dp[c], dp[c + coeurOrdre] + gainOrdre);
  }
  int sol = *max_element(dp.begin(), dp.end());
  cout << sol << endl;
}

• Subtask 1: 18 / 18
• Subtask 2: 18 / 18
• Subtask 3: 18 / 18
• Subtask 4: 18 / 18
• Subtask 5: 18 / 18
• Subtask 6: 10 / 10