oj.uz

Submission #348593

# Submission time Handle Problem Language Result Execution time Memory
348593 2021-01-15T09:08:30 Z Halogen Detecting Molecules (IOI16_molecules) C++14
0 / 100
 45 ms 65540 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Runtime error 45 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 43 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 45 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 45 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 45 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 45 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -