제출 #775398

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
775398		Ludissey	Detecting Molecules (IOI16_molecules)	C++14	31 / 100	546 ms	65536 KiB

molecules

#include "molecules.h"
#include <iostream>
#include <string>
#include <set>
#include <map>
#include <cstring>
#include <unordered_map>
#include <vector>
#include <fstream>
#include <bitset>
#include <tuple>
#include <cmath>
#include <cstdint>
#include <stack>
#include <cassert>
#include <cstdio>
#include <queue>
#include <iterator>
#include <iomanip>
#include <algorithm>
#include <sstream>

using namespace std;
int l, u;
vector<pair<int, int>> w_sort;
vector<int> out;
unordered_map<string, int> memo;
int dp(int i, int mx, int mn, long long sum) {
    string key = to_string(i) + "_" + to_string(mx) + "_" + to_string(mn) + "_" + to_string(sum);
    if (memo.count(key))
        return memo[key];

    if (sum > u || (mx - mn > u - l && mx != 0))
        return memo[key] = 0;

    if (sum >= l)
        return memo[key] = 1;

    if (i < 0)
        return memo[key] = 0;

    if (dp(i - 1, max(mx, w_sort[i].first), min(mn, w_sort[i].first), sum + w_sort[i].first)) {
        out.push_back(w_sort[i].second);
        return memo[key] = 1;
    }
    else if (dp(i - 1, mx, mn, sum)) {
        return memo[key] = 1;
    }

    return memo[key] = 0;
}
std::vector<int> find_subset(signed _l, signed _u, std::vector<int> w) {
    l = _l;
    u = _u;
    int n = w.size();
    w_sort.resize(n);
    vector<int> prefx(n+1);
    for (int i = 0; i < n; i++) w_sort[i] = {w[i],i};
    sort(w_sort.begin(), w_sort.end());
    if (dp(n - 1, 0, 10000000, 0)) {
        return out;
    }
    return std::vector<int>(0);
}

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