제출 #307272

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
307272		mihai145	Detecting Molecules (IOI16_molecules)	C++14	19 / 100	1090 ms	768 KiB

molecules

#include "molecules.h"
#include <vector>
#include <bitset>
 
const int DIM = 1100000;
std::bitset <DIM> s;
 
std::vector<int> find_subset(int l, int u, std::vector<int> w) {
    std::vector <int> ans;
 
    s[0] = 1;
 
    for(auto it : w)
      	if(it <= u)
        s |= (s << it);
 
    int p = -1;
    for(int pos = l; pos <= u; pos++)
        if(s[pos] == 1)
            {
                p = pos;
                break;
            }
 
    if(p == -1)
        return ans;
 
    int pointerW = (int)w.size() - 1;
 
    while(p > 0)
        {
            while(pointerW >=0 && (p - w[pointerW] < 0 || s[p - w[pointerW]] != 1))
                pointerW--;
 
            if(pointerW >= 0) {
                ans.push_back(pointerW);
                p -= w[pointerW];
                pointerW--;
            }
        }
 
    return ans;
}

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