Submission #443850

#	Time	Username	Problem	Language	Result	Execution time	Memory
443850		BT21tata	Detecting Molecules (IOI16_molecules)	C++17	31 / 100	50 ms	65540 KiB

molecules

#include "molecules.h"
#include<bits/stdc++.h>
#define F first
#define S second
#define pb push_back
using namespace std;

vector<int> p[500005];
vector<pair<int,int> >a;
int ans;
bool sum[500005];

vector<int> find_subset(int l, int r, vector<int> w)
{
    for(int i=0; i<(int)w.size(); i++)
        a.pb({w[i], i});
    sort(a.begin(), a.end());
    sum[0]=1;
    for(pair<int,int> u : a)
    {
        for(int i=r; i>=0; i--)
        {
            if(sum[i] and i+u.F<=r and !sum[i+u.F])
            {
                sum[i+u.F]=1;
                p[i+u.F]=p[i];
                p[i+u.F].pb(u.S);
                if(l<=i+u.F and i+u.F<=r)
                {
                    ans=i+u.F;
                    break;
                }
            }
        }
        if(ans) break;
    }
    return p[ans];
}

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