Submission #864414

#	Time	Username	Problem	Language	Result	Execution time	Memory
864414		dpsaveslives	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	42 ms	9680 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
using namespace std;
 
vector<int> find_subset(int l, int u, vector<int> w){
    vector<pair<ll,int>> sorted; int n = (int)(w.size());
    for(int i = 0;i<n;++i) sorted.push_back({w[i],i});
    sort(sorted.begin(),sorted.end());
    ll sum = sorted[0].f;
    int j = 0, st = -1, ed = -1; vector<int> ans;
    for(int i = 0;i<n;++i){
        while(j+1 < n && sum+sorted[j+1].f < l){
            sum += sorted[j+1].f;
            ++j;
        }
        if(j+1 < n && sum < l){
            sum += sorted[j+1].f;
            ++j;
        }
        if(l <= sum && sum <= u){
            st = i; ed = j;
            break;
        }
        sum -= sorted[i].f;
    }
    if(st != -1){
        vector<int> ans;
        for(int i = st;i <= ed;++i){
            ans.push_back(sorted[i].s);
        }
        return ans;
    }
    return ans;
}

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