제출 #757810

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
757810		taher	Cloud Computing (CEOI18_clo)	C++17	100 / 100	717 ms	2388 KiB

clo

#include <bits/stdc++.h>

using namespace std;

struct Elem {
  long long id, sz, freq, val;
  bool operator<(const Elem &autre) {
    if (freq == autre.freq) {
      return id < autre.id;      
    }
    return freq < autre.freq;
  }
};

vector<Elem> v;
int N;

const int MaxN = 2000 + 1;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  int mes = 0;
  for (int i = 0; i < n; i++) {
    long long a, b, c;
    cin >> a >> b >> c;
    mes += a;
    v.push_back({2, a, b , c});
  }
  int m;
  cin >> m;
  for (int i = 0; i < m; i++) {
    long long a, b, c;
    cin >> a >> b >> c;
    mes += a;
    v.push_back({1, a, b, c});
  }
  sort(v.rbegin(),v.rend());
  N = m + n;
  bool reachable[MaxN * 2 * 50 + 10];
  long long dp[MaxN * 2 * 50 + 10];
  memset(reachable, 0, sizeof(reachable));
  for (int i = 0; i < MaxN * 2 * 50 + 10; i++) {
    dp[i]= -(long long)1e18;
  }
  reachable[0] = true;
  dp[0] = 0;
  for (int i = 0; i < N; i++) {
    Elem ext = v[i];
    if (ext.id == 2) {
      for (int j = mes; j >= 0; j--) {
        long long add_t = ext.sz;
        long long gain = ext.val * -1;
        if (j + add_t >= 0 && reachable[j]) {
          reachable[j + add_t] = true;
          dp[j + add_t] = max(dp[j + add_t], dp[j] + gain);
        }
      }
    }
    else{
      for (int j = 0; j <= mes; j++) {
        long long add_t = ext.sz * -1;
        long long gain = ext.val;
        if (j + add_t >= 0 && reachable[j]) {
          reachable[j + add_t] = true;
          dp[j + add_t] = max(dp[j + add_t], dp[j] + gain);
        }
      }
    }
  }
  long long best = 0;
  for (int i = 0; i <= mes; i++) {
    best = max(best, dp[i]);
  }
  cout << best << '\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