Submission #599835

#	Time	Username	Problem	Language	Result	Execution time	Memory
599835		cheissmart	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	45 ms	4672 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7;

vi find_subset(int l, int r, vi w) {
    int n = SZ(w);
    vi p(n); iota(ALL(p), 0);
    sort(ALL(p), [&] (int x, int y) {
        return w[x] < w[y];
    });
    V<ll> s(n + 1);
    for(int i = 1; i <= n; i++)
        s[i] = s[i - 1] + w[p[i - 1]];
    for(int len = 1; len <= n; len++) {
        ll x = s[len], y = s[n] - s[n - len];
        if(y < l || x > r) continue; 
        for(int i = 1; i + len - 1 <= n; i++) {
            if(l <= s[i + len - 1] - s[i - 1] && s[i + len - 1] - s[i - 1] <= r) {
                vi ans;
                for(int j = i; j <= i + len - 1; j++)
                    ans.PB(p[j - 1]);
                return ans;
            }
        }
    }
    return {};
}

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