제출 #1245160

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1245160		hayford08	Nile (IOI24_nile)	C++20	67 / 100	2095 ms	4936 KiB

nile

#include <iostream>
#include <vector>
#include <ranges>
#include <algorithm>
#include <numeric>
#include <set>
using namespace std;

vector<long long> subTask5(const vector<int> &W, const vector<int> &A, const vector<int> &B, const vector<int> &E) {
  int n = W.size();
  vector<array<int, 2>> arr(n);
  long long base = 0;
  for (int i = 0; i < n; i++) {
    arr[i] = {W[i], A[i] - B[i]};
    base += B[i];
  }
  ranges::sort(arr);

  auto compute = [&](int l, int r, int D) -> long long { 
    int len = r - l + 1;
    if (len % 2 == 0) {
      return 0LL;
    }
    int cost = 1e9;
    for (int i = l; i <= r; i++) {
      // remove i 
      int szLeft = i - l;
      if ((szLeft % 2 == 0) || (i - 1 >= l && i + 1 <= r && arr[i + 1][0] - arr[i - 1][0] <= D)) {
        cost = min(cost, arr[i][1]);
      }
      // (pair i - 1 and i) or (i and i + 1)
      else {
        cost = min(cost, min(arr[i - 1][1], arr[i + 1][1]));
      }
    }
    return cost;
  };

  int q = E.size();
  vector<long long> res(q, base);
  for (int i = 0; i < q; i++) {
    int D = E[i];
    int pos = 0;
    while (pos < n) {
      int l = pos, r = pos++;
      while (pos < n && arr[pos][0] - arr[pos - 1][0] <= D) {
        r = pos++;
      }
      res[i] += compute(l, r, D);
    }
  }
  return res;
}


std::vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
  return subTask5(W, A, B, E);
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 11 / 11
• Subtask 5: 20 / 20
• Subtask 6: 0 / 15
• Subtask 7: 0 / 18