Submission #742380

#	Time	Username	Problem	Language	Result	Execution time	Memory
742380		oyber	Detecting Molecules (IOI16_molecules)	C++14	46 / 100	333 ms	65536 KiB

molecules

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

using namespace std;

vector<int> find_subset(int l, int u, vector<int> w) {
    int n = int(w.size());
    vector<vector<int>> sums(u+1, vector<int>(0));

    for (int i = 0; i < n; i++) {
        for (int j = u; j > 0; j--) {
            int k = j-w[i];
            if (k < 0) continue;
            if (int(sums[j].size()) > 0) continue;
            if (k == 0) sums[j] = {i};
            if (int(sums[k].size()) > 0) {
                sums[j] = sums[k];
                sums[j].push_back(i);
            }
        }
    }

    for (int i = l; i <= u; i++) {
        if (int(sums[i].size()) > 0) {
            return sums[i];
        }
    }

    return vector<int>(0);
}

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