oj.uz

Submission #673618

# Submission time Handle Problem Language Result Execution time Memory
673618 2022-12-21T12:42:01 Z MADE_IN_HEAVEN Bank (IZhO14_bank) C++17
0 / 100
 3 ms 392 KB 
#include <bits/stdc++.h>
using namespace std;
#define what(a) cout << (#a) << " is " << (a) << '\n';

const int N = 20;
string s;
int  n , m , a[N] , b[N];
pair<int , int> memo[1 << N];
bool visited[1 << N];

pair<int , int> dp(int mask) {

  if (mask == 0) {
    return make_pair(0 , 0);
  }

  if (visited[mask])
    return memo[mask];

  pair<int , int> res = make_pair(-1 , -1);

  for (int i = 0; i < m; i++) if(mask & (1 << i)) {
    auto prev = dp(mask - (1 << i));
    if(prev.first == -1 || prev.second == -1) continue;

    int pos = prev.first;

    if(prev.second + b[i] < a[pos]) res = max(res , make_pair(prev.first , prev.second + b[i]));
    if(prev.second + b[i] == a[pos]) res = max(res , make_pair(prev.first + 1 , 0));
  }

  visited[mask] = true;
  memo[mask] = res;

  if(res.first == n) {
    cout << "YES";
    exit(0);
  }

  return res;
}

void solve() {

  cin >> n >> m;

  for(int i = 0 ; i < n ; i++) cin >> a[i];
  for(int i = 0 ; i < m ; i++) cin >> b[i];

  dp((1 << m) - 1);

  cout << "NO";

  return;
}

int main() {

  freopen("bank.in" , "r" , stdin);
  freopen("bank.out" , "w" , stdout);

  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  int tt = 1;
  // cin >> tt;
  while (tt--) {
    solve();
  }

  return 0;
}

Compilation message

bank.cpp: In function 'int main()':
bank.cpp:59:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |   freopen("bank.in" , "r" , stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bank.cpp:60:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |   freopen("bank.out" , "w" , stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 392 KB Output isn't correct
2 Halted 0 ms 0 KB -