Submission #1129395

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129395		dr.rabi3	Bank (IZhO14_bank)	C++20	100 / 100	458 ms	164600 KiB

bank

// #pragma GCC optimize ("O3")
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
#define int long long
#define ed '\n'
using namespace std;

constexpr int N = 20;
int n , m;
vector<int>pref , v;
int dp [ 1 << N ][ N ];
int best( int idx , int mask ) {
  if ( idx == n ) return 1;
  int sum = 0 , & ret = dp [ mask ][ idx ];
  if ( ~ret ) return ret;
  ret = 0;
  for ( int i = 0; i < m; i++ )
    sum += v [ i ] * ( mask >> i & 1 );
  for ( int i = 0; i < m; i++ ) {
    if ( mask >> i & 1 ) continue;
    if ( sum + v [ i ] > pref [ idx ] ) continue;
    int x = sum + v [ i ];
    ret |= best( idx + ( x == pref [ idx ] ) , mask | 1 << i );
    }
  return ret;
  }

void doWork( int TC ) {
  cin >> n >> m;
  pref = vector<int>( n );
  v = vector<int>( m );
  for ( auto& i : pref ) cin >> i;
  for ( auto& i : v ) cin >> i;
  for ( int i = 1; i < n; i++ ) pref [ i ] += pref [ i - 1 ];
  memset( dp , -1 , sizeof( dp ) );
  cout << ( best( 0 , 0 ) ? "YES" : "NO" );
  }

int32_t main( ) {
  ios_base::sync_with_stdio( false );
  cout.tie( nullptr );
  cin.tie( nullptr );
// #ifndef ONLINE_JUDGE
//   freopen( "input.txt" , "r" , stdin );
//   freopen( "output.txt" , "w" , stdout );
// #else
//   // freopen("banana.in", "r", stdin);
//   // freopen("gcd.out", "w", stdout);
// #endif
  int _ = 1;
  // cin >> _;
  for ( int __ = 1; __ <= _; __++ ) {
    // cout << "Case " << __ << ":\n";
    doWork( __ );
    if ( __ < _ ) cout << '\n';
    // cout << '\n';
    }
  return 0;
  }

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