Submission #781365

#	Time	Username	Problem	Language	Result	Execution time	Memory
781365		devariaota	Detecting Molecules (IOI16_molecules)	C++17	0 / 100	33 ms	65536 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>
// #define int long long
using namespace std;
vector <int> p;
int lower,up;
int memo[10005][10005];
vector<int> ans;
int n,v;
int dp (int indeks, int sisa){
    if (indeks>=n) return 0;
    if (memo[indeks][sisa]!=-1) return memo[indeks][sisa];
    memo[indeks][sisa]=dp(indeks+1,sisa);
    if (sisa-p[indeks]>=0){
        memo[indeks][sisa]=max(memo[indeks][sisa],p[indeks]+dp(indeks+1,sisa-p[indeks]));
    }
    return memo[indeks][sisa];
}
void bt (int indeks, int sisa){
    if (indeks>=n) return;
    if (dp(indeks,sisa)==dp(indeks+1,sisa)){
        bt(indeks+1,sisa);
    }
    else{
        ans.push_back(indeks);
        bt(indeks+1,sisa-p[indeks]);
    }
}
std::vector<int> find_subset(int l, int u, std::vector<int> w) {
    memset(memo,-1,sizeof(memo));
    p=w;
    lower=l,up=u;
    n=w.size();
    v=dp(0,u);
    // cout<<v<<"::"<<"::"<<n<<endl;
    if (v<l){
        return ans;
    }
    bt(0,u);
    return ans;
}

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