Submission #1269915

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269915		julia_08	Cloud Computing (CEOI18_clo)	C++20	0 / 100	62 ms	120136 KiB

clo

#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;
}

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