Submission #74236

#	Time	Username	Problem	Language	Result	Execution time	Memory
74236		imeimi2000	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	84 ms	6940 KiB

molecules

#include "molecules.h"
#include <algorithm>

using namespace std;
typedef long long llong;
typedef pair<int, int> pii;

vector<int> find_subset(int l, int u, vector<int> w) {
    vector<pii> ws;
    int n = w.size();
    for (int i = 0; i < n; ++i) ws.emplace_back(w[i], i);
    sort(ws.begin(), ws.end());
    vector<llong> sum;
    sum.push_back(0);
    for (int i = 0; i < n; ++i) sum.push_back(sum.back() + ws[i].first);
    for (int i = 1; i <= n; ++i) {
        llong mn = sum[i];
        llong mx = sum[n] - sum[n - i];
        if (mx < l || u < mn) continue;
        for (int j = i; j <= n; ++j) {
            llong v = sum[j] - sum[j - i];
            if (l <= v && v <= u) {
                vector<int> ret;
                for (int k = j - i; k < j; ++k) ret.push_back(ws[k].second);
                return ret;
            }
        }
    }
    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: 31 / 31