Submission #1006927

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006927		christinelynn	Cloud Computing (CEOI18_clo)	C++17	100 / 100	272 ms	1372 KiB

clo

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;
const int max_cores = 1e5, maxx = 4e3, inf = 1e15;
bool debug = 0;

// merge the buying and selling phase arrays into one and sort based on the clock rate so we can solve it in a single state array dp
// dp[i] = max(dp[i], dp[i-cores] - v)
// dp[i] = max(dp[i], dp[i+cores] + v) 
// initiate dp[i] = -inf
// dp[i] = maximum profit if there are i cores in demand

struct komputer {
  int cor, fre, val;
  bool pes;
};

int n, m;
komputer kom[maxx+5];
int dp[max_cores+5];

bool cmp(komputer a, komputer b) {
  if (a.fre != b.fre) return a.fre > b.fre;
  return a.pes < b.pes;
}

signed main() {
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  cin >> n;
  for (int i=1; i<=n; i++) {
    cin >> kom[i].cor >> kom[i].fre >> kom[i].val;
    kom[i].pes = 0;
  }
  cin >> m;
  for (int i=1; i<=m; i++) {
    cin >> kom[n+i].cor >> kom[n+i].fre >> kom[n+i].val;
    kom[n+i].pes = 1;
  }
  for (int i=1; i<=max_cores; i++) dp[i] = -inf;
  sort(kom+1, kom+n+m+1, cmp);
  dp[0] = 0;
  for (int i=1; i<=n+m; i++) {
    if (kom[i].pes) {
      for (int j = 0; j <= max_cores - kom[i].cor; j++) {
        dp[j] = max(dp[j], dp[j+kom[i].cor]+kom[i].val);
      }
    }
    else {
      for (int j=max_cores; j>=kom[i].cor; j--) {
        dp[j] = max(dp[j], dp[j-kom[i].cor]-kom[i].val);
      }
    }
  }
  int ans = 0;
  for (int i=0; i<=max_cores; i++) {
//    cout << i << " cores -> " << dp[i] << endl;
    ans = max(dp[i], ans);
  }
  cout << ans << endl;
  return 0;
}

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