제출 #762263

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
762263		NeroZein	Cloud Computing (CEOI18_clo)	C++17	100 / 100	494 ms	2056 KiB

clo

#include "bits/stdc++.h"
#define int long long
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

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

const int N = 4003;
const int MX = 2000 * 50 + 1; 

sth a[N];
int pd[MX];
int dp[MX]; 

signed main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    int c, f, v;
    cin >> c >> f >> v;
    a[i] = {c, f, -v};
  }
  int m;
  cin >> m;
  for (int i = 1; i <= m; ++i) {
    int c, f, v;
    cin >> c >> f >> v;
    a[i + n] = {-c, f, v}; 
  }
  sort(a + 1, a + n + m + 1, [&](const sth& x, const sth& y) {
    return (x.f == y.f ? x.c > y.c : x.f > y.f); 
  });
  fill(pd + 1, pd + MX, -1e15); 
  for (int i = 1; i <= n + m; ++i) {
    auto [c, f, v] = a[i]; 
    for (int j = 0; j < MX; ++j) {
      dp[j] = pd[j]; 
    }
    if (c < 0) {//order
      for (int j = 0; j - c < MX; ++j) {
        dp[j] = max(dp[j], pd[j - c] + v); 
      }
    } else {
      for (int j = c; j < MX; ++j) {
        dp[j] = max(dp[j], pd[j - c] + v);
      }
    }
    for (int j = 0; j < MX; ++j) {
      pd[j] = dp[j]; 
    }
  }
  int ans = 0; 
  for (int i = 0; i < MX; ++i) {
    ans = max(ans, dp[i]);
  }
  cout << ans << '\n'; 
  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