Submission #352252

#	Time	Username	Problem	Language	Result	Execution time	Memory
352252		retsiger	Bank (IZhO14_bank)	C++14	100 / 100	274 ms	21100 KiB

bank

#include<bits/stdc++.h>

using namespace std;

const int INF = 1e9;

int N, M;
int S[22], A[22], B[22];
bool dp[(1 << 20)][20];

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
//  freopen("cc.inp", "r", stdin);
  //freopen("cc.out", "w", stdout);
  cin >> N >> M;
  for (int i = 0; i < N; ++i) {
    cin >> A[i];
    S[i] = S[i - 1] + A[i];
  }
  for (int i = 0; i < M; ++i) cin >> B[i];
  dp[0][0] = true;
  for (int msk = 0; msk < (1 << M); ++msk) {
    int sum = 0;
    for (int i = 0; i < M; ++i) if (msk >> i & 1)
      sum += B[i];
    for (int K = 0; K < N; ++K) if (dp[msk][K]) {
      for (int i = 0; i < M; ++i) if (!(msk >> i & 1)) {
        int nmsk = msk | (1 << i);
        if (sum + B[i] <= S[K]) dp[nmsk][K] = true;
        if (sum == S[K] && B[i] <= A[K + 1]) dp[nmsk][K + 1] = true;
      }
    }
  }
  for (int msk = 0; msk < (1 << M); ++msk) {
    int sum = 0;
    for (int i = 0; i < M; ++i) if (msk >> i & 1)
      sum += B[i];
    if (sum == S[N - 1] && dp[msk][N - 1]) {
      cout << "YES";
      return 0;
    }
  }
  cout << "NO";
  return 0;
}

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