Submission #1006895

#TimeUsernameProblemLanguageResultExecution timeMemory
1006895makanhuliaCloud Computing (CEOI18_clo)C++17
100 / 100
257 ms1532 KiB
#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";
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...