#include "molecules.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 5e5 + 10;
int dp[MAXN];
vector<int> solve(int l, int u, vector<pair<int, int>> &W){
ll sum = 0;
vector<int> ans;
for(int i=0; i<W.size(); i++){
sum += W[i].first;
if(l <= sum && sum <= u){
for(int j=0; j<=i; j++) ans.push_back(W[j].second);
return ans;
}
if(sum > u){
if(l <= sum - W[0].first && sum - W[0].first <= u){
for(int j=1; j<=i; j++) ans.push_back(W[j].second);
return ans;
}
}
}
return {};
}
vector<int> find_subset(int l, int u, vector<int> w){
if(l > u) return {};
vector<pair<int, int>> W;
for(int i=0; i<w.size(); i++) W.push_back({w[i], i});
sort(W.begin(), W.end());
if(W[0].first > u) return {};
for(auto x : W){
if(l <= x.first && x.first <= u){
return {x.second};
}
}
if(W[0].first <= u - l) return solve(l, u, W);
for(int i=0; i<W.size(); i++){
for(int j=i+1; j<W.size(); j++){
if(l <= W[i].first + W[j].first && W[i].first + W[j].first <= u){
vector<int> ans = {W[i].second, W[j].second};
return ans;
}
}
}
for(int i=0; i<=u; i++) dp[i] = 1e9;
dp[0] = 0;
int val = -1;
for(int i=1; i<=W.size(); i++){
auto [x, j] = W[i - 1];
bool ok = false;
for(int k=u; k>=x; k--){
if(dp[k - x] != 1e9){
dp[k] = min(dp[k], i);
if(k >= l){
ok = true;
val = k;
break;
}
}
}
if(ok) break;
}
if(val == -1) return {};
vector<int> ans;
for(int j=W.size(); j>=1; j--){
if(W[j - 1].first <= val && dp[val - W[j - 1].first] < j){
ans.push_back(W[j - 1].second);
val -= W[j - 1].first;
}
}
return ans;
}
Compilation message (stderr)
molecules.h:1:9: warning: #pragma once in main file
1 | #pragma once
| ^~~~
molecules_c.h:1:9: warning: #pragma once in main file
1 | #pragma once
| ^~~~
# | 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... |