제출 #1013991

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1013991		vjudge1	은행 (IZhO14_bank)	C++17	100 / 100	145 ms	8788 KiB

bank

//#pragma GCC optimize("Ofast,O3,unroll-loops")
//#pragma comment(linker, "/SET: 2000000")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define bp __builtin_popcountll
#define mp make_pair
#define pb push_back
#define vec vector
#define ll long long
#define F first
#define S second
#define ld long double
#define pii pair <int, int>
#define elif else if
#define sz(a) int32_t(a.size())
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(), a.end()
#define fl fflush(stdout)
#define ex exit(0)
#define pll pair <ll, ll>
#define int ll
#define FOR(i, l, r) for(int i = l; i <= r; ++i)
#define ROF(i, l, r) for(int i = r; i >= l; --i)
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define ti tuple<int, int, int>
//#define FELIX
using namespace std;
using namespace __gnu_pbds;
template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rnd(228355);
const int N = 21;
const int M = (1 << N);
int d[M], a[N], b[N], n, m;

void solve(){
    cin >> n >> m;
    FOR(i, 0, n - 1) cin >> a[i];
    FOR(i, 0, m - 1) cin >> b[i];

    FOR(i, 1, n - 1){
        a[i] += a[i - 1];
    }
    a[n] = 1e9;

    int mx = -1;

    int cur = (1 << m) - 1;
    //cout << "CUR: " << cur << "\n";

    FOR(i, 0, cur){

        int sum = 0;
        FOR(j, 0, m - 1){
            int x = (1 << j);
            if((i & x)) sum += b[j];
        }

        FOR(j, 0, m - 1){
            int x = (1 << j);

            if(!(i & x)){

                if(sum + b[j] == a[d[i]]){
                    d[i ^ x] = max(d[i ^ x], d[i] + 1);
                }
                if(sum + b[j] < a[d[i]]){
                    d[i ^ x] = max(d[i ^ x], d[i]);
                }

            }

        }

        mx = max(mx, d[i]);
    }

    if(mx == n) cout << "YES";
    else cout << "NO";
}

signed main(){
#ifdef FELIX
	auto _clock_start = chrono::high_resolution_clock::now();
#endif

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

	int t = 1;
	//cin >> t;
	while(t--) solve();

#ifdef FELIX
	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
		chrono::high_resolution_clock::now()
			- _clock_start).count() << "ms." << endl;
#endif
}

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