제출 #1006895

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1006895		makanhulia	Cloud Computing (CEOI18_clo)	C++17	100 / 100	257 ms	1532 KiB

clo

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m, inf = 1e15;
priority_queue<pair<pair<int, int>, pair<int, int>>> pq;
int dp[200005];
int c, f, v, a, ran = 0;
signed main() {
  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  for(int i = 1; i <= 100000; i++) {
    dp[i] = inf;
  }
  cin >> n;
  for(int i = 0; i < n; i++) {
    cin >> c >> f >> v;
    pq.push({{f, 2}, {c, v}});
  }
  cin >> m;
  for(int i = 0; i < m; i++) {
    cin >> c >> f >> v;
    pq.push({{f, 1}, {c, v}});
  }
  
  while(!pq.empty()) {
    c = pq.top().second.first;
    v = pq.top().second.second;
    a = pq.top().first.second;
    pq.pop();
    if(a == 2) {
      for(int i = 100000; i >= 0; i--) {
        dp[i + c] = min(dp[i + c], dp[i] + v);
      }
      
      ran += c;
    } else {
      for(int i = c; i <= 100000; i++) {
        dp[i - c] = min(dp[i - c], dp[i] - v);
      }
    }
  }
  int mini = 0;
  for(int i = 0; i <= 100000; i++) {
    mini = min(dp[i], mini);
  }
  mini *= -1;
  cout << mini << "\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