Submission #1138155

#TimeUsernameProblemLanguageResultExecution timeMemory
1138155AliyyiakbarDetecting Molecules (IOI16_molecules)C++20
9 / 100
3 ms3656 KiB
#include "molecules.h" #include "bits/stdc++.h" using namespace std; vector<int> find_subset(int l, int r, vector<int> w) { int n = w.size(); vector<int> indices; int sum = accumulate(w.begin(), w.end(), 0LL); vector<vector<bool>> dp(n + 1, vector<bool>(sum + 1)); vector<vector<int>> parent(n + 1, vector<int>(sum + 1, -1)); dp[0][0] = true; for (int i = 1; i <= n; ++i) { for (int j = 0; j <= sum; ++j) { dp[i][j] = dp[i-1][j]; if (j >= w[i-1] && dp[i-1][j-w[i-1]]) { dp[i][j] = true; parent[i][j] = j - w[i-1]; } } } for (int sm = l; sm <= r; ++sm) { if (dp[n][sm]) { int current = sm; for (int i = n; i > 0; --i) { if (parent[i][current] != -1) { indices.push_back(i-1); current = parent[i][current]; } } return indices; } } return {}; }

Compilation message (stderr)

molecules.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
molecules_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...