Submission #493287

#	Time	Username	Problem	Language	Result	Execution time	Memory
493287		Alex_tz307	Cloud Computing (CEOI18_clo)	C++17	100 / 100	1089 ms	1868 KiB

clo

#include <bits/stdc++.h>

using namespace std;

const int kN = 4e3;
const int64_t INF = 1e18L;

struct transaction {
  int c, f, v;

  void read() {
    cin >> c >> f >> v;
  }

  bool operator < (const transaction &rhs) const {
    if (f != rhs.f) {
      return f > rhs.f;
    }
    return c > rhs.c;
  }
} a[kN];

void maxSelf(int64_t &x, int64_t y) {
  if (x < y) {
    x = y;
  }
}

void testCase() {
  int n;
  cin >> n;
  int N = 0;
  for (int i = 0; i < n; ++i) {
    a[i].read();
    a[i].v = -a[i].v;
    N += a[i].c;
  }
  int m;
  cin >> m;
  for (int i = n; i < n + m; ++i) {
    a[i].read();
    a[i].c = -a[i].c;
  }
  n += m;
  sort(a, a + n);
  vector<int64_t> dp(N + 1, -INF);
  dp[0] = 0;
  for (int i = 0; i < n; ++i) {
    vector<int64_t> newDp = dp;
    for (int j = 0; j <= N; ++j) {
      if (dp[j] != -INF) {
        int k = j + a[i].c;
        if (0 <= k && k <= N) {
          maxSelf(newDp[k], dp[j] + a[i].v);
        }
      }
    }
    dp = newDp;
  }
  cout << *max_element(dp.begin(), dp.end()) << '\n';
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int tests = 1;
  for (int tc = 0; tc < tests; ++tc) {
    testCase();
  }
  return 0;
}

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