Submission #565056

#	Time	Username	Problem	Language	Result	Execution time	Memory
565056		MadokaMagicaFan	Detecting Molecules (IOI16_molecules)	C++14	31 / 100	1083 ms	10508 KiB

molecules

#include "bits/stdc++.h"

using namespace std;

using ll = long long;
const ll inf = 1e9;
const int md1 = 1e9+7;

#define all(v)                      v.begin(), v.end()
#define rall(v)                     v.rbegin(), v.rend()
#define sz(v)                       ((int)v.size())

#define forn(i,n)                   for(int i = 0; i < n; ++i)
#define forbe(i,b,e)                for(int i = b; i < e; ++i)

#define pb                          push_back

#define pry                         puts("YES")
#define prn                         puts("NO")
#define endl                        '\n'

#define fst                         first
#define scn                         second

int
find_subset(int *l)
{
    return 0;
}

vector<int>
find_subset(int l, int r, vector<int> w)
{
    int n = sz(w);
    map<int,int> p;
    set<ll> vals;
    vals.insert(0);
    p[0] = -1;

    vector<ll> ws;
    ll ans = -1;
    for (int i = 0; i < n; ++i) {
        ws.clear();

        for (auto u : vals)
            ws.pb(u+w[i]);

        for (auto u : ws) {
            if (vals.find(u) == vals.end())
                p[u] = i;
            vals.insert(u);

            if (l <= u && r >= u){
                ans = u;
                i = n;
                break;
            }
        }
    }

    vector<int> result;
    if (ans == -1)
        return result;

    while (p[ans] != -1) {
        result.pb(p[ans]);
        ans = ans - w[p[ans]];
    }

    return result;
}

#ifdef ONPC
void
solve()
{

    const int N = 1e4;
    int n, l, r;

    cin >> n >> l >> r;
    int w[N];
    for (int i = 0; i < n; ++i)
        cin >> w[i];
    int result[N];

    int ans = find_subset(l,r,w,n, result);

    cout << ans << endl;
    return;
    for (int i = 0; i < ans; ++i) {
        cout << w[result[i]-1] << ' ';
    }
    cout << endl;
}

int32_t
main()
{
    freopen("in", "r", stdin);
    int t = 1;
    cin >> t;
    while(t--)
        solve();
}
#endif

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