Submission #428959

#	Time	Username	Problem	Language	Result	Execution time	Memory
428959		LouayFarah	Detecting Molecules (IOI16_molecules)	C++14	0 / 100	1091 ms	204 KiB

molecules

#include "bits/stdc++.h"
#include "molecules.h"
using namespace std;
 
#define pb push_back
 
int n, l, u;
vector<int> w;
vector<int> backtrack;
vector<int> pre;
 
bool solve(int i, int curr)
{
    if(curr>=l&&curr<=u)
        return true;
    if(i==n)
        return false;
    if(curr>u)
        return false;
 
    int temp = 0;
    if(i==0)
        temp = curr + pre[n-1];
    else
        temp = curr + pre[n-1]-pre[i-1];
 
    if(temp<l)
        return false;
 
    bool flag = false;
    for(int j = i; j<n; j++)
    {
        backtrack.pb(j);
        flag = solve(j+1, curr+w[j]);
        if(flag)
            break;
        backtrack.pop_back();
    }
    return flag;
}
 
vector<int> find_subset(int L, int U, vector<int> W)
{
    n = (int)W.size();
    l = L;
    u = U;
    w = W;
 
    sort(w.begin(), w.end(), greater<int>());
    
    pre.assign(n, 0);
    pre[0] = w[0];
    for(int i = 1; i<n; i++)
        pre[i] = pre[i-1] + w[i];
 
    bool flag = solve(0, 0);
 
    if(flag)
    {
        vector<int> result = backtrack;
        return result;
    }
 
    vector<int> result(0);
    return result;
}

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