Submission #348593

#	Time	Username	Problem	Language	Result	Execution time	Memory
348593		Halogen	Detecting Molecules (IOI16_molecules)	C++14	0 / 100	45 ms	65540 KiB

molecules

#include <bits/stdc++.h>
#include "molecules.h"

using namespace std;

bitset<10005> dp[10005];
int memo[10005][10005];
vector<int> weights, ans;

bool find(int W, int index) {
  if (index == 0 || W == 0) {
    ans.clear();
    return true;
  }
  if (W < 0) return false;
  if (memo[W][index] != -1) return memo[W][index];

  // printf("%d %d\n", W, weights[index - 1]);

  if (dp[index - 1].test(W)) {    
    if (find(W, index - 1)) {
      return memo[W][index] = true;
    }
  }

  if (weights[index - 1] > W) return memo[W][index] = false;
  if (dp[index - 1].test(W - weights[index - 1])) {
    if (find(W - weights[index - 1], index - 1)) {
      ans.push_back(index);
      return memo[W][index] = true;
    }
  }
  return memo[W][index] = false;
}

std::vector<int> find_subset(int l, int u, std::vector<int> w) {
  int N = w.size();
  memset(memo, -1, sizeof(memo));
  for (int i = 0; i < N; i++) weights.push_back(w[i]);
  memset(dp, 0, sizeof(dp));
  dp[0].set(0, 1);

  for (int i = 0; i < N; i++) dp[i + 1] = (dp[i] | (dp[i] << w[i]));

  for (int i = l; i < u; i++) {
    if (!dp[N].test(i)) continue;
    find(i, N);
    break;
  }

  return ans;
}

Compilation message (stderr)

molecules.cpp: In function 'bool find(int, int)':
molecules.cpp:22:29: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   22 |       return memo[W][index] = true;
      |              ~~~~~~~~~~~~~~~^~~~~~
molecules.cpp:26:53: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   26 |   if (weights[index - 1] > W) return memo[W][index] = false;
      |                                      ~~~~~~~~~~~~~~~^~~~~~~
molecules.cpp:30:29: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   30 |       return memo[W][index] = true;
      |              ~~~~~~~~~~~~~~~^~~~~~
molecules.cpp:33:25: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   33 |   return memo[W][index] = false;
      |          ~~~~~~~~~~~~~~~^~~~~~~

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