제출 #775393

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
775393		Ludissey	Detecting Molecules (IOI16_molecules)	C++14	0 / 100	1084 ms	340 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;
int dp(int i, int mx, int mn ,long long sum) {
    if (sum > u || (mx - mn > u - l&&mx!=0)) return 0;
    if (sum >= l) return 1;
    if (i < 0) return 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 1;
    }
    else if (dp(i - 1, mx, mn, sum)) {
        return 1;
    }
    return 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: 0 / 9
• Subtask 2: 0 / 10
• Subtask 3: 0 / 12
• Subtask 4: 0 / 15
• Subtask 5: 0 / 23
• Subtask 6: 0 / 31