Submission #1269930

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269930		julia_08	Cloud Computing (CEOI18_clo)	C++20	54 / 100	151 ms	327680 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 = 2e3 + 10;
const int INF = 1e18;

computer comp[MAXN], ord[MAXN];

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

  int n; cin >> n;

  int max_c = 0;

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

  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;
    max_c = max(max_c, ord[i].c);
  } 

  int dp[2][n + 1][m + 1][max_c + 1];

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

  for(int i=0; i<=n; i++){
    for(int j=0; j<=m; j++){
      for(int k=0; k<=max_c; k++){
        dp[0][i][j][k] = dp[1][i][j][k] = -INF;
      }
    }
  }

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

  // observação interessante:
  // sempre temos que k = comp[i].c ou l = ord[j].c :)

  /*
    0 -> k = comp[i].c
    1 -> l = ord[j].c
  */

  for(int i=1; i<=n; i++){

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

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

    for(int j=1; j<=m; j++){

      // dp[0]:

      int k = comp[i].c;

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

        dp[0][i][j][l] = max(
          dp[1][i][j - 1][k], // nao pego o j
          dp[0][i - 1][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[0][i][j][l] = max(dp[0][i][j][l], dp[1][i][j - 1][k - l] + ord[j].v - cost);

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

      }

      // dp[1]:

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

        int l = ord[j].c;

        dp[1][i][j][k] = max(
          dp[1][i][j - 1][k], // nao pego o j
          dp[0][i - 1][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[1][i][j][k] = max(dp[1][i][j][k], dp[1][i][j - 1][k - l] + ord[j].v - cost);

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

      }

    }
  } 

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

  return 0;
}

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