Submission #591178

#	Time	Username	Problem	Language	Result	Execution time	Memory
591178		jackkkk	Cloud Computing (CEOI18_clo)	C++17	100 / 100	395 ms	1356 KiB

clo

// Cloud Computing
// https://oj.uz/problem/view/CEOI18_clo


#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <array>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
#include <list>
#include <float.h>
#include <climits>
#include <iomanip>
#include <chrono>

using namespace std;
using namespace std::chrono;

void quit() {
  cout.flush();
  exit(0);
}

struct entry {
  int c;
  int f;
  long long int v;
  bool operator< (const entry& other) const {
    if (f != other.f) {
      return f > other.f;
    }
    return c > other.c;
  }
};


int n, m;
vector<entry> entries;

constexpr int MAXDP = 100001;

long long int dp[MAXDP + 1];


int main(void){
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  entry te;

  cin >> n;
  for (int i = 0; i < n; ++i) {
    cin >> te.c >> te.f >> te.v;
    te.v *= -1;
    entries.push_back(te);
  }

  cin >> m;
  for (int i = 0; i < m; ++i) {
    cin >> te.c >> te.f >> te.v;
    te.c *= -1;
    entries.push_back(te);
  }
  sort(entries.begin(), entries.end());

  for (int i = 0; i < MAXDP; ++i) {
    dp[i] = -9999999999999LL;
  }
  dp[0] = 0;


  for (const auto& entry : entries) {
    if (entry.c > 0) { // machine
      for (int i = MAXDP - 1; i >= entry.c; --i) {
        dp[i] = max(dp[i], dp[i - entry.c] + entry.v);
      }
    } else { // job
      for (int i = 0; i <= MAXDP - 1 + entry.c; ++i) {
        dp[i] = max(dp[i], dp[i - entry.c] + entry.v);
      }
    }
  }

  long long int ans = 0;
  for (int i = 0; i < MAXDP; ++i) {
    ans = max(ans, dp[i]);
  }

  cout << ans << std::endl;
  
  quit();
}

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