Submission #926189

#	Time	Username	Problem	Language	Result	Execution time	Memory
926189		sano	Bank (IZhO14_bank)	C++17	100 / 100	101 ms	16984 KiB

bank

#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <algorithm>
#include <cstdlib>
#include <random>
#include <stack>
#include <fstream>
//#include <popcntintrin.h> // Include the header file for __builtin_popcount
#define ll long long
#define For(i, n) for(ll i = 0; i < n; ++i)
#define ffor(i, a, n) for(ll i = a; i < n; ++i)
#define pb push_back
#define vec vector 
#define ff first
#define ss second
#define pairs pair<ll, ll>
#define NEK 2000000000
#define mod 1000000007
#define vel 1000
using namespace std;
typedef unsigned short int sui;

ll __builtin_popcountmoje(ll x) {
    ll num = 0;
    while (x) {
        num += x & 1;
        x /= 2;
    }
    return num;
}

bool zorad(pair<ll, vec<ll>> a, pair<ll, vec<ll>> b) {
    return a.ff > b.ff;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //ifstream cin("movie.in");
    //ofstream cout("movie.out");
    int n, m;
    cin >> n >> m;
    vec<int> a;
    vec<int> b;
    For(i, n) {
        int x;
        cin >> x;
        a.push_back(x);
    }
    For(i, m) {
        int x;
        cin >> x;
        b.push_back(x);
    }
    bool mame = false;
    vec<pairs> dp((1 << m), { NEK, NEK });
    dp[0] = { 0, 0 };
    ffor(i, 1, (1 << m)) {
        For(j, m) {
            if (!(i & (1 << j))) continue;
            pairs novy = dp[i - (1<<j)];
            if (novy.ff >= n) continue;
            novy.ss += b[j];
            if (novy.ss == a[novy.ff]) {
                novy.ff++;
                novy.ss = 0;
            }
            else {
                if (novy.ss > a[novy.ff]) {
                    novy = { NEK, NEK };
                }
            }
            if(novy.ff != NEK) {
                dp[i] = novy;
                if (dp[i].ff == n && dp[i].ss == 0) {
                    mame = true;
                }
            }
        }
    }
    string s = "NO";
    if (mame) s = "YES";
    cout << s << '\n';
    return 0;
}

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