Submission #1269915

#TimeUsernameProblemLanguageResultExecution timeMemory
1269915julia_08Cloud Computing (CEOI18_clo)C++20
0 / 100
62 ms120136 KiB
#include <bits/stdc++.h>
#define int long long

using namespace std;

struct computer{

  int c, f, v, i;

  bool operator < (computer other){
    if(f != other.f) return f > other.f;
    return i < other.i;
  }

};

const int MAXN = 250;
const int INF = 1e18;

computer comp[MAXN], ord[MAXN];

int dp[MAXN][51][MAXN][51];

int32_t main(){
  cin.tie(0)->sync_with_stdio(0);

  int n; cin >> n;

  for(int i=1; i<=n; i++){
    cin >> comp[i].c >> comp[i].f >> comp[i].v;
    comp[i].i = i;
  }

  int m; cin >> m;

  for(int i=1; i<=m; i++){
    cin >> ord[i].c >> ord[i].f >> ord[i].v;
    ord[i].i = i;
  }

  sort(comp + 1, comp + n + 1);
  sort(ord + 1, ord + m + 1);

  for(int i=0; i<=n; i++){
    for(int k=0; k<=comp[i].c; k++){
      for(int j=0; j<=m; j++){
        for(int l=0; l<=ord[j].c; l++){
          dp[i][k][j][l] = -INF;
        }
      }
    }
  }

  dp[0][0][0][0] = 0;

  for(int i=1; i<=n; i++){
    for(int k=0; k<=comp[i].c; k++){

      dp[i][k][0][0] = 0;

      for(int j=1; j<=m; j++){
        for(int l=0; l<=ord[j].c; l++){

          dp[i][k][j][l] = max(
            dp[i][k][j - 1][ord[j - 1].c], // nao pego o j
            dp[i - 1][comp[i - 1].c][j][l] // nao uso o computador i 
          );

          if(comp[i].f < ord[j].f) continue;

          int cost = (k == comp[i].c ? comp[i].v : 0);

          if(k >= l){
            dp[i][k][j][l] = max(dp[i][k][j][l], dp[i][k - l][j - 1][ord[j - 1].c] + ord[j].v - cost);

          } else{
            dp[i][k][j][l] = max(dp[i][k][j][l], dp[i - 1][comp[i - 1].c][j][l - k] - cost);
          }

          // cout << i << " " << k << " " << j << " " << l << " -> " << dp[i][k][j][l] << "\n";

        }
      }

    }
  }

  cout << dp[n][comp[n].c][m][ord[m].c] << "\n";

  return 0;
}
#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...