제출 #1351901

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1351901		bbbiros	Detecting Molecules (IOI16_molecules)	C++20	46 / 100	1094 ms	5504 KiB

molecules

#include "molecules.h"
#include <unordered_map>
#include <iostream>
#include <algorithm>
using namespace std;
unordered_map<int, int> m;
vector<int> find_subset(int l, int u, vector<int> w)
{
    m[0] = -1;
    int ans = 0;
    vector<int> v={0};
    for(int i=0;i<w.size();i++)
    {
        vector<int> v1(0);
        for(int x:v)
        {
            if(x+w[i]>u)continue;
            if(m.count(x+w[i]))continue;
            m[x+w[i]]=i;
            v1.push_back(x+w[i]);
        }
        for(int x:v1)v.push_back(x);
    }
    for(int i=0;i<v.size();i++)
    {
        if(v[i]>=l)
        {
            ans=v[i];
        }
    }
    if (ans == 0)
        return {};
    vector<int> ansv;
    while (ans > 0)
    {
        ansv.push_back(m[ans]);
        ans -= w[ansv.back()];
    }
    reverse(ansv.begin(),ansv.end());
    return ansv;
}

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