oj.uz

Submission #752643

# Submission time Handle Problem Language Result Execution time Memory
752643 2023-06-03T11:11:02 Z I_love_Daneliya Bank (IZhO14_bank) C++17
19 / 100
 157 ms 82388 KB 
// Madi abi crush !
#include <bits/stdc++.h>
using namespace std ;

#define ll long long
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)

const int N = 1e5 + 1 ;

int n , m , a[20] , b[20] ;
ll pref[20] ;

int dp[20][(1 << 20) + 1] ;

// 1 5
// 8
// 4 2 5 1 3 

bool go(int i , int mask , ll cur) {
   if (cur == pref[i]) {
      i++ , dp[i][mask] = 1 ;
   }
   if (i >= n) {
      cout << "YES\n" ;
      exit(0) ;
   }
   if (~dp[i][mask]) return dp[i][mask] ;
   bool ans = 0 ;
   for (int j = 0;  j < m ; j++) {
      if ((mask >> j & 1) == 0) {
         ans = max(ans , go(i , (mask | (1 << j)) , cur + b[j])) ;
      }
   }
   dp[i][mask] = ans ;
   return ans ;
}

void solve() {
   memset(*dp, -1, sizeof(dp)) ;
   cin >> n >> m ;
   for (int i = 1 ; i <= n ; i++) {
      cin >> a[i - 1] ;
   }
   for (int i = 0 ; i < n ; i++) {
      if (i) pref[i] = pref[i - 1] ;
      pref[i] += a[i] ;
   }
   for (int i = 1 ; i <= m ; i++) {
      cin >> b[i - 1] ;
   }
   go(0,0,0) ;
      cout << "NO\n" ;
}

int main() {
   ios::sync_with_stdio(false) ;
   cin.tie(0) ;
   int test = 1 ;
   // cin >> test ;
   for (int i = 1 ; i <= test ; i++) {
      solve() ;
   }
   return 0 ;
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 82276 KB Output is correct
2 Correct 38 ms 82344 KB Output is correct
3 Correct 36 ms 82388 KB Output is correct
4 Correct 34 ms 82268 KB Output is correct
5 Correct 157 ms 82384 KB Output is correct
6 Correct 37 ms 82328 KB Output is correct
7 Correct 35 ms 82348 KB Output is correct
8 Correct 35 ms 82380 KB Output is correct
9 Correct 148 ms 82380 KB Output is correct

Subtask #2
0 / 25.0

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

Subtask #3
0 / 27.0

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

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 82276 KB Output is correct
2 Correct 38 ms 82344 KB Output is correct
3 Correct 36 ms 82388 KB Output is correct
4 Correct 34 ms 82268 KB Output is correct
5 Correct 157 ms 82384 KB Output is correct
6 Correct 37 ms 82328 KB Output is correct
7 Correct 35 ms 82348 KB Output is correct
8 Correct 35 ms 82380 KB Output is correct
9 Correct 148 ms 82380 KB Output is correct
10 Incorrect 38 ms 82308 KB Output isn't correct
11 Halted 0 ms 0 KB -