제출 #296713

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
296713		Haunted_Cpp	Detecting Molecules (IOI16_molecules)	C++17	69 / 100	1041 ms	4600 KiB

molecules

#include <bits/stdc++.h>

#include "molecules.h"
using namespace std;

vector<int> find_subset(int lo, int hi, vector<int> w) {
  const int n = w.size();
  vector<pair<int, int>> arr(n);
  for (int i = 0; i < n; i++) {
    arr[i] = {w[i], i};
  }
  sort(arr.begin(), arr.end());
  vector<long long> dp(n);
  dp[0] = arr[0].first;
  for (int i = 1; i < n; i++) {
    dp[i] = arr[i].first + dp[i - 1];
  }
  auto range_sum = [&](int l, int r) {
    return dp[r] - (l - 1 >= 0 ? dp[l - 1] : 0);
  };
  for (int t = 1; t <= n; t++) {
    long long s = 0;
    for (int i = 0; i <= t; i++) {
      const int suf = t - i;
      long long add = range_sum(n - suf, n - 1);
      if (suf >= 1) s += add;
      if (s >= lo && s <= hi) {
        vector<int> res;
        for (int x = 0; x < i; x++) {
          res.emplace_back(arr[x].second);
        }
        for (int x = n - suf; x < n; x++) {
          res.emplace_back(arr[x].second);
        }
        return res;
      }
      s -= add;
      s += arr[i].first;
    }
  }
  return vector<int>();
}

• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 15 / 15
• Subtask 5: 23 / 23
• Subtask 6: 0 / 31