Submission #334153

#	Time	Username	Problem	Language	Result	Execution time	Memory
334153		AlexLuchianov	Bank (IZhO14_bank)	C++14	100 / 100	193 ms	4716 KiB

bank

#include <iostream>
#include <vector>
#include <cassert>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 20;
int const lim = 20000;
int v[1 + nmax], sum[1 + nmax], bank[1 + nmax];
int spec[1 + lim];
int dp[(1 << nmax)];

int main() {
  int n, m;
  std::cin >> n >> m;
  for(int i = 1;i <= n; i++) 
    std::cin >> v[i];
  for(int i = 1;i <= n; i++)
    sum[i] = sum[i - 1] + v[i];
  for(int i = 1;i <= n; i++)
    spec[sum[i]] = i;
  
  for(int j = 0; j < m; j++)
    std::cin >> bank[j];

  for(int i = 1;i <= lim; i++)
    if(spec[i] == 0)
      spec[i] = spec[i - 1];
  dp[0] = 1;
  bool valid = false;
  for(int mask = 0; mask < (1 << m); mask++) 
    if(dp[mask] == 1) {
      int cost = 0;
      for(int j = 0; j < m; j++)
        if(0 < ((1 << j) & mask))
          cost += bank[j];
      for(int j = 0; j < m; j++)
        if(0 == ((1 << j) & mask)) {
          int cost2 = cost + bank[j];
          int mask2 = mask | (1 << j);
          if(spec[cost] == spec[cost2])
            dp[mask2] = dp[mask];
          else if(spec[cost] + 1 == spec[cost2] && sum[spec[cost2]] == cost2) {
            dp[mask2] = dp[mask];
            if(spec[cost2] == n)
              valid = true;
          }
        }
    }

  if(valid == true)
    std::cout << "YES\n";
  else
    std::cout << "NO\n";
  return 0;
}

• Subtask 1: 19 / 19
• Subtask 2: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29