Submission #715684

#	Time	Username	Problem	Language	Result	Execution time	Memory
715684		adrilen	Detecting Molecules (IOI16_molecules)	C++17	0 / 100	1 ms	212 KiB

molecules

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;

#include "molecules.h"

constexpr int maxu = 1e4 + 5;

int last[maxu] = { 0 };

bool found[maxu] = { 0 };

std::vector<int> find_subset(int l, int u, std::vector<int> w) {
    
    
    found[0] = true;

    int highest = 0;

    int p;

    for (int v : w)
    {
        for (int i = highest; i >= 0; i--)
        {
            if (!found[i]) continue;
            // cout << i << endl;
            if (i + v >= maxu) continue;

            if (found[i + v]) continue;

            found[i + v] = true;
            last[i + v] = v;

            if (l <= i + v && i + v <= u) {
                p = i + v;
                goto finish;
            }
        }
        highest += v;
    }

    return vector<int>{};

    finish:

    vector <int> output;

    // int i = 15;
    while (p != 0)
    {
        output.emplace_back(last[p]);
        // cout << "p" << p << endl;
        p -= last[p];
    }

    return output;
}

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