제출 #906439

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
906439		vjudge1	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	46 ms	9668 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using vi = vector<int>;
using ii = pair<ll, ll>;

vi find_subset(int l, int u, vi w) {
    vector<ii> V;
    for(int i = 0; i < int(w.size()); ++i)
        V.push_back({w[i], i});
    sort(V.begin(), V.end());
    ll s = 0, d = -1, sum = 0, n = int(w.size());
    while(d + 1 < n && sum + V[d + 1].first <= u) {
        sum += V[d + 1].first;
        ++d;
    }
    while(sum < l) {
        if(d + 1 < n) {
            sum += V[d + 1].first - V[s].first;
            ++d;
            ++s;
        } else break;
    }
    if(sum >= l && sum <= u) {
        vi re;
        for(int i = s; i <= d; ++i) {
            re.push_back(V[i].second);
        }
        return re;
    }
    return vi();
}

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