oj.uz

답안 #702676

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
702676 2023-02-24T18:40:30 Z GrizzyCoder79c Cloud Computing (CEOI18_clo) C++14
0 / 100
 3000 ms 32980 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 1236 KB Output is correct
5 Correct 19 ms 11200 KB Output is correct
6 Incorrect 6 ms 8520 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Execution timed out 3039 ms 816 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 1076 KB Output is correct
4 Correct 1 ms 1108 KB Output is correct
5 Execution timed out 3065 ms 2104 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Execution timed out 3059 ms 32980 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 6 ms 2616 KB Output is correct
3 Incorrect 149 ms 32392 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 1236 KB Output is correct
5 Correct 19 ms 11200 KB Output is correct
6 Incorrect 6 ms 8520 KB Output isn't correct
7 Halted 0 ms 0 KB -