Submission #397121

#	Time	Username	Problem	Language	Result	Execution time	Memory
397121		ollel	Cloud Computing (CEOI18_clo)	C++17	0 / 100	135 ms	262148 KiB

clo

#include <bits/stdc++.h>
using namespace std;

#define rep(i,a,b) for(int i = a; i < b; i++)
#define pb push_back
#define INF 1e18

typedef vector<int> vi;
typedef long long ll;

struct comp {
  int cost, cores, speed;
  comp(int cst, int crs, int s) {cost = cst; cores = crs; speed = s;}
  comp() {};
};

int n, m;
int MAXCORES = 50 * 2000 + 100;

int main()
{
  cin >> n;
  vector<comp> store(n);
  rep(i,0,n) cin >> store[i].cores >> store[i].speed >> store[i].cost;
  cin >> m;
  vector<comp> customer(m);
  rep(i,0,m) cin >> customer[i].cores >> customer[i].speed >> customer[i].cost;

  sort(store.begin(), store.end(), [](comp a, comp b) {
    return ((float)a.cores / (float)a.cost > (float)b.cores / (float)b.cost);
  });

  vector<vector<ll>> kns(n, vector<ll>(MAXCORES, INF));
  kns[0][store[0].cores] = store[0].cost;
  kns[0][0] = 0;
  rep(i,1,n) {
    rep(c, 0, store[i].cores) {
      kns[i][c] = kns[i - 1][c];
    }
    rep(c, store[i].cores, MAXCORES) {
      kns[i][c] = min(kns[i - 1][c], kns[i - 1][c - store[i].cores] + store[i].cost);
    }
  }

  sort(customer.begin(), customer.end(), [](comp b, comp a) {
    return ((float)a.cores / (float)a.cost > (float)b.cores / (float)b.cost);
  });

  vector<vector<ll>> knc(m, vector<ll>(MAXCORES, -INF));
  knc[0][customer[0].cores] = customer[0].cost;
  knc[0][0] = 0;
  rep(i,1,m) {
    rep(c, 0, customer[i].cores) {
      knc[i][c] = knc[i - 1][c];
    }
    rep(c, customer[i].cores, MAXCORES) {
      knc[i][c] = max(knc[i - 1][c], knc[i - 1][c - customer[i].cores] + customer[i].cost);
    }
  }

  for (int i = MAXCORES - 2; i; i--) kns[n - 1][i] = min(kns[n - 1][i], kns[n - 1][i + 1]);


  ll ans = 0;
  rep(i, 0, MAXCORES) {
    ans = max(ans, knc[m - 1][i] - kns[n - 1][i]);
  }

  cout << ans;
}

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