Submission #702676

#	Time	Username	Problem	Language	Result	Execution time	Memory
702676		GrizzyCoder79c	Cloud Computing (CEOI18_clo)	C++14	0 / 100	3065 ms	32980 KiB

clo

#include <bits/stdc++.h>

using namespace std;

struct Element {
  int c, f, v;
  bool operator < (Element o) const {
    if(f != o.f) {
      return f > o.f;
    } else if(c != o.c) {
      return c > o.c;
    } else {
      return v > o.v;
    }
  }
};

int const INF = 1e9;
int const NMAX = 2000;
int const MMAX = 2000;
int const KMAX = 4000;
int const CMAX = 10000;
int n, m;
Element e[1 + KMAX];
int dp[1 + KMAX][1 + CMAX];
int k, cmax;

int computeDP(int i, int j) {
  if(j > cmax) {
    dp[i][j] = -INF;
  } else if(i == 0) {
      dp[i][j] = (j == 0 ? 0 : -INF);
  } else if(dp[i][j] == -INF) {
    //cout << "(" << i << ", " << j << ") -> (" << i-1 << ", " << j << ") : " << computeDP(i-1, j) << "\n";
    dp[i][j] = computeDP(i-1, j);
    if(j-e[i].c >= 0) {
      //cout << "(" << i << ", " << j << ") -> (" << i-1 << ", " << j-e[i].c << ") : " << computeDP(i-1, j-e[i].c)+e[i].v << "\n";
      dp[i][j] = max(dp[i][j], computeDP(i-1, j-e[i].c)+e[i].v);
    }
  }
  return dp[i][j];
}

int main() {
  cin >> n;
  for(int i = 1; i <= n; i++) {
    int c, f, v;
    cin >> c >> f >> v;
    e[++k] = {c, f, -v};
    cmax += c;
  }
  cin >> m;
  for(int i = 1; i <= m; i++) {
    int c, f, v;
    cin >> c >> f >> v;
    e[++k] = {-c, f, v};
  }
  sort(e+1, e+k+1);
  for(int i = 1; i <= k; i++) {
    for(int c = 0; c <= cmax; c++) {
      dp[i][c] = -INF;
    }
  }
  int ans = 0;
  for(int c = 0; c <= cmax; c++) {
    //cout << "(" << k << ", " << c << "):" << " " << computeDP(k, c) << "\n";
    ans = max(ans, computeDP(k, c));
  }
  cout << ans << "\n";
}

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