oj.uz

답안 #397123

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
397123 2021-05-01T13:45:15 Z ollel Cloud Computing (CEOI18_clo) C++17
18 / 100
 433 ms 4400 KB 
#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(2, 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&1][c] = kns[(i&1)^1][c];
    }
    rep(c, store[i].cores, MAXCORES) {
      kns[i&1][c] = min(kns[(i&1)^1][c], kns[(i&1)^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(2, 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&1][c] = knc[(i&1)^1][c];
    }
    rep(c, customer[i].cores, MAXCORES) {
      knc[i&1][c] = max(knc[(i&1)^1][c], knc[(i&1)^1][c - customer[i].cores] + customer[i].cost);
    }
  }

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


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

  cout << ans;
}

Subtask #1
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4156 KB Output is correct
2 Correct 3 ms 4156 KB Output is correct
3 Correct 15 ms 4156 KB Output is correct
4 Correct 24 ms 4156 KB Output is correct
5 Incorrect 200 ms 4156 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4156 KB Output is correct
2 Incorrect 5 ms 4156 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 4228 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 4156 KB Output is correct
2 Correct 5 ms 4156 KB Output is correct
3 Correct 192 ms 4148 KB Output is correct
4 Correct 193 ms 4264 KB Output is correct
5 Correct 389 ms 4256 KB Output is correct
6 Correct 425 ms 4312 KB Output is correct
7 Correct 419 ms 4300 KB Output is correct
8 Correct 433 ms 4400 KB Output is correct

Subtask #5
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4156 KB Output is correct
2 Incorrect 20 ms 4232 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4156 KB Output is correct
2 Correct 3 ms 4156 KB Output is correct
3 Correct 15 ms 4156 KB Output is correct
4 Correct 24 ms 4156 KB Output is correct
5 Incorrect 200 ms 4156 KB Output isn't correct
6 Halted 0 ms 0 KB -