Submission #781336

#	Time	Username	Problem	Language	Result	Execution time	Memory
781336		devariaota	Detecting Molecules (IOI16_molecules)	C++17	0 / 100	1 ms	340 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll memo[10005];
ll up,lower,v;
vector <int> ans;
int n;
vector <int > p;
ll dp (ll indeks){
    // cout<<indeks<<endl;
    if (indeks>=n) {
        memo[indeks]=0;
        return 0;
    }
    if (indeks==n-1){
        memo[indeks]=p[indeks];
        return p[indeks];
    }
    if (memo[indeks]!=-1) return memo[indeks];
    for (int i=indeks+1;i<=n;i++){
        memo[indeks]=max(dp(i),memo[indeks]);
        if (dp(i)+p[indeks]<=up){
            memo[indeks]=max(memo[indeks],dp(i)+p[indeks]);
        }
    }
    // cout<<indeks<<" "<<memo[indeks]<<endl;
    return memo[indeks];
}
void bt (ll indeks){
    if (indeks>=n) return;
    if (indeks==n-1){
        ans.push_back(n-1);
        return;
    }
    for (int i=indeks+1;i<n;i++){
        if (v==dp(i)){
            bt(i);
            break;
        }
        else if (v==dp(i)+p[indeks]){
            ans.push_back(indeks);
            bt(i);
            break;
        }
        // if (v==dp(i)+p[indeks]){
        //     ans.push_back(indeks);
        //     bt(i);
        //     break;
        // }
    }
}
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();
    p.push_back(0);

    v=dp(0);
    // cout<<v<<"::"<<dp(4)<<"::"<<n<<endl;
    if (v<l){
        return ans;
    }
    bt(0);
    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