Submission #28950

#TimeUsernameProblemLanguageResultExecution timeMemory
28950h0ngjun7Detecting Molecules (IOI16_molecules)C++14
100 / 100
99 ms5336 KiB
#include "molecules.h" #include <algorithm> using namespace std; typedef long long ll; int n, w[200005], c[200005]; inline bool cmp(const int &a, const int &b) { return w[a] < w[b]; } vector<int> find_subset(int l, int u, vector<int> _w) { vector <int> ans = {}; for (auto &t : _w) c[n] = n, w[n++] = t; sort(c, c + n, cmp); if (w[c[0]] > u) return ans; ll s = 0; int left = 0, right = 0; for (int i = 0; i < n; i++) { if (s + w[c[i]] > u) break; s += w[c[i]]; right = i; } if (right == n - 1 && s < l) return ans; while (right + 1 <= n - 1 && !(l <= s && s <= u)) { s += w[c[++right]]; while (left <= right && s > u) s -= w[c[left++]]; } if (l <= s && s <= u) { for (int i = left; i <= right; i++) ans.push_back(c[i]); } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...