이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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) {
if (l >= n) return 0LL;
return dp[r] - (l - 1 >= 0 ? dp[l - 1] : 0LL);
};
long long s = 0;
for (int i = 0; i <= n; i++) {
int l = i + 1;
int r = n;
while(l < r) {
const int mid = l + (r - l) / 2;
long long add = range_sum(mid, n - 1);
if (s + add <= hi) r = mid;
else l = mid + 1;
}
s += range_sum(r, n - 1);
if (s >= lo && s <= hi) {
vector<int> res;
for (int x = 0; x < i; x++) {
res.emplace_back(arr[x].second);
}
for (int x = r; x < n; x++) {
res.emplace_back(arr[x].second);
}
return res;
}
s += arr[i].first;
s -= range_sum(r, n - 1);
}
return vector<int>();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |