Submission #758982

#	Time	Username	Problem	Language	Result	Execution time	Memory
758982		scrge	Bank (IZhO14_bank)	C++17	52 / 100	67 ms	18752 KiB

bank

#include <bits/stdc++.h>
using namespace std;
const int N = 20;

int n, m;
int salary[N], notes[N], pref[N+1];
int dp[1 << N], sum[1 << N];

signed main(){
  cin >> n >> m;
  int cur_pref = 0;
  pref[0] = 0;
  for(int i = 0; i < n; i++){
    cin >> salary[i];
    //cur_pref += salary[i];
    pref[i+1] = pref[i] + salary[i];
  }
  for(int i = 0; i < m; i++){
    cin >> notes[i];
  }

  for(int i = 0; i < (1 << m); i++){
    int cur = 0;
    for(int j = 0; j < m; j++){
      if(i & (1 << j)) cur += notes[j];
    }
    sum[i] = cur;
  }

  vector<int> masks[N];
  for(int i = 0; i < (1 << m); i++)
    masks[__builtin_popcount(i)].push_back(i);

  memset(dp, 0, sizeof dp);
  dp[0] = true;
  for(int i = 0; i < m; i++){
    for(int mask: masks[i]){
      for(int j = 0; j < m; j++){
        if((mask & (1 << j)) || !dp[mask]) continue;
        int nmask = mask | (1 << j);

        auto lb1 = upper_bound(pref, pref+n, sum[mask]);
        auto lb2 = upper_bound(pref, pref+n, sum[nmask]);
        lb1--, lb2--;
        if(lb1 != lb2){
          if(lb2 == next(lb1) && *lb2 == sum[nmask])
            dp[nmask] = true;
        } else{
          dp[nmask] = true;
        }
      }
      //cout << bitset<6>(mask) << " " << dp[mask] << endl;
    }
  }

  bool ans = false;
  for(int mask = 0; mask < (1 << m); mask++){
    if(sum[mask] == pref[n]){
      //printf("mask %d has sum equals %d, dp = %d\n", mask, pref[n], dp[mask]);
    } 
    if(sum[mask] == pref[n] && dp[mask])
      ans = true;
  }
  if(ans)
    cout << "YES";
  else
    cout << "NO";
}

Compilation message (stderr)

bank.cpp: In function 'int main()':
bank.cpp:11:7: warning: unused variable 'cur_pref' [-Wunused-variable]
   11 |   int cur_pref = 0;
      |       ^~~~~~~~

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