Submission #1031292

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031292		Tonyl	Detecting Molecules (IOI16_molecules)	C++17	46 / 100	17 ms	25436 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define REP(i,n) for (int i = 0; i < n; i++)

const int MAX_N = 10002;
const int MAX_L = 10002;

using b = bitset<MAX_L>;
b history[MAX_N];

std::vector<int> find_subset(int l, int u, std::vector<int> w) {
    history[0][0] = 1;
    int n = w.size();
    REP(i,n) {
        history[i+1] = history[i] | (history[i]<<w[i]);
    }

    // find sol
    int goal = -1;
    for (int i = l; i <= u; i++) {
        if (history[n][i]) goal = i;
    }
    
    if (goal == -1) return {};
    
    vi sel;
    int i = n;
    while (goal > 0) {
        while (history[i-1][goal]) i--;
        sel.push_back(i-1);
        goal -= w[i-1];
    }

    return sel;
}

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