Submission #537934

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
537934	2022-03-15 22:20:12	nicolexxuu	Bank (IZhO14_bank)	C++14	100 / 100	92 ms	8508 KiB

bank

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
#define MAXN 21
using namespace std;
int N, M;
int a[MAXN], b[MAXN];
int num_people[1 << MAXN], leftover[1 << MAXN];
int main() {
  cin >> N >> M;
  for(int i = 0; i < N; i++) cin >> a[i];
  for(int i = 0; i < M; i++) cin >> b[i];
  
  bool ok = false;
  for(int mask = 0; mask < (1 << M); mask++) {
    int p = num_people[mask];
//    cout << "mask: " << mask << " p: " << p << "leftover: " << leftover[mask] << endl;
    ok |= (p == N);
    if(mask > 0 && (p == 0 && leftover[mask] == 0)) continue;
    for(int note = 0; note < M; note++) {
      if((mask & (1 << note)) == 0) {
        int new_mask = mask + (1 << note);
        if(leftover[mask] + b[note] < a[p]) {
          num_people[new_mask] = p;
          leftover[new_mask] = leftover[mask] + b[note];
//          cout << "new mask: " << new_mask << " p: " << p << "leftover: " << leftover[new_mask] << endl;
        } else if(leftover[mask] + b[note] == a[p]) {
          num_people[new_mask] = p+1;
          leftover[new_mask] = 0;
//          cout << "new mask: " << new_mask << " p: " << p+1 << endl;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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