Submission #717663

#	Time	Username	Problem	Language	Result	Execution time	Memory
717663		Toxtaq	Detecting Molecules (IOI16_molecules)	C++17	19 / 100	1 ms	468 KiB

molecules

#include<bits/stdc++.h>
#include "molecules.h"
using namespace std;
vector<int> find_subset(int l, int r, vector<int>w){
    int n = w.size();
    vector<vector<long long>>table(n + 1, vector<long long>(n + 1, -1e15));
    vector<vector<pair<int, int>>>par(n + 1, vector<pair<int, int>>(n + 1, {-1, -1}));
    /// table[k][i] -> max_weight <= r we can get if we choose k weights from first i weights
    /// table[k][i] = max(min(r, table[k - 1][i - 1] + w[i]), table[k][i - 1])
    table[0][0] = 0;
    for(int k = 1;k <= n;++k){
        for(int i = 1;i <= n;++i){
            table[0][i] = 0;
            table[k][i] = table[k][i - 1];
            par[k][i] = {k, i - 1};
            long long tempo = table[k - 1][i - 1] + w[i - 1];
            if(tempo <= r && table[k][i] < tempo){
                table[k][i] = tempo;
                par[k][i] = {k - 1, i - 1};
            }
//            cout << "table[" << k << "][" << i << "]=" << table[k][i] << ", {" << par[k][i].first << ", " << par[k][i].second << "}\n";
        }
    }
    pair<int, int>num = {-1, -1};
    for(int i = 1;i <= n;++i){
        if(table[i][n] >= l){num = {i, n};break;}
    }
    vector<int>ans;
    while(num.first > 0){
        int k = num.first, i = num.second;
        pair<int, int>tempo = {k - 1, i - 1};
        if(par[k][i] == tempo){
            ans.push_back(i - 1);
        }
        num = par[k][i];
    }
    return ans;
}

//int main()
//{
//    int l, r, n;
//    cin >> l >> r >> n;
//    vector<int>v(n);
//    for(int i = 0;i < n;++i)cin >> v[i];
//    vector<int>ans = find_subset(l, r, v);
//    for(int i : ans)cout << i << " ";
//}

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