Submission #1084870

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084870		serpent_121	Bank (IZhO14_bank)	C++17	100 / 100	147 ms	8788 KiB

bank

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <numeric>
#include <cmath>
#include <cstring>
#include <climits>
#include <stack>
#include <bitset>
typedef long long ll;
using namespace std;
#define fst first
#define snd second

// kazakh oly
// https://oj.uz/problem/view/IZhO14_bank
int main() {
   ll n, m; cin >> n>> m;
   ll a[n]; ll b[m]; ll pref[n];
   for (int i = 0 ; i<n; i++) {
        cin >> a[i];
        if (i==0) pref[0] = a[0];
        else pref[i] = pref[i-1] + a[i];
   }
   for (int i = 0; i<m; i++) cin >> b[i];
   ll dp[1<<m]; dp[0] = -1; bool ans = false;
   for (int x = 1; x<(1<<m); x++) {
        dp[x] = -1; ll sum = 0;
        for (int k = 0; k<m; k++) if (x & (1<<k)) sum+= b[k];
        for (int k = 0; k<m; k++) {
            if (x & (1<<k)) {
                if (dp[x ^ (1<<k)]>=0 && (sum - pref[dp[x ^ (1<<k)]]< a[dp[x ^ (1<<k)] + 1]) ) dp[x] = dp[x ^ (1<<k)];
                else if (dp[x ^ (1<<k)]==-1 && (sum < a[0]) ) dp[x] = -1;
                else if (dp[x ^ (1<<k)]==-1 && (sum == a[0]) ) dp[x] = 0;
                else if (dp[x ^ (1<<k)]>=0 && (sum - pref[dp[x ^ (1<<k)]]== a[dp[x ^ (1<<k)] + 1]) ) dp[x] = dp[x ^ (1<<k)] + 1;
            }
        }
        if (dp[x]==n-1) {
            ans = true; break;
        }
   }
   if (ans) cout << "YES"; 
   else cout << "NO";
   
}

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