Submission #1023296

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023296		ventusliberum	Cloud Computing (CEOI18_clo)	C++17	100 / 100	470 ms	2200 KiB

clo

/**
 *    title:  Cloud Computing
**/
#include <bits/stdc++.h>
using namespace std;

#define si(x) int(x.size())
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define overload(a, b, c, d, ...) d
#define rep0(n) for (int _ = 0; _ < (n); _++)
#define rep1(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); i++)
#define rrep1(i, n) for (int i = (n) - 1; i >= 0; i--)
#define rrep2(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define rep(...) overload(__VA_ARGS__, rep2, rep1, rep0)(__VA_ARGS__)
#define rrep(...) overload(__VA_ARGS__, rrep2, rrep1)(__VA_ARGS__)
template <class T, class U> inline bool chmax(T &a, U b) { return (a < b ? a = b, 1 : 0); }
template <class T, class U> inline bool chmin(T &a, U b) { return (b < a ? a = b, 1 : 0); }
template <class T> istream &operator>>(istream &is, vector<T> &v) { for (auto &x : v) is >> x; return is; }
template <class T> ostream &operator<<(ostream &os, const vector<T> &v) { rep(i, si(v)) os << (i ? " " : "") << v[i]; return os; }
using ll = long long;
constexpr int inf = 1001001001;
constexpr long long infll = 4004004004004004004LL;

struct T {
  int c, f, v;
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  int n;
  cin >> n;
  vector<T> use;
  int S = 0;
  rep(n) {
    int c, f, v;
    cin >> c >> f >> v;
    S += c;
    v = -v;
    use.push_back({c, f, v});
  }
  int m;
  cin >> m;
  rep(m) {
    int c, f, v;
    cin >> c >> f >> v;
    c = -c;
    use.push_back({c, f, v});
  }
  sort(all(use), [&](auto &x, auto &y) {
    return x.f != y.f ? x.f > y.f : x.c > y.c;
  });
  vector<ll> dp(S+1, -infll);
  dp[0] = 0;
  for (auto [c, f, v] : use) {
    auto ndp = dp;
    rep(i, S+1) {
      if (dp[i] == -infll) continue;
      if (i + c >= 0) {
        chmax(ndp[i+c], dp[i] + v);
      }
    }
    swap(dp, ndp);
  }
  cout << *max_element(all(dp)) << '\n';
}

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