제출 #1178285

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1178285		zyadhany	은행 (IZhO14_bank)	C++20	100 / 100	202 ms	8520 KiB

bank

#include <bits/stdc++.h>
#include <chrono>
#include <random>
#include <unordered_map>
#include <unordered_set>
 
#define ll long long
#define vi vector<ll>
#define vii vector<vi>
#define pl pair<ll, ll>
#define all(X) X.begin(),X.end()
#define vp vector<pl>
#define mi map<ll,ll>
 
#define ld long double
#define vc vector<char>
#define vcc vector<vc>
#define mc map<char,int>
#define sortx(X) sort(X.begin(),X.end());
#define allr(X) X.rbegin(),X.rend()
#define ln '\n'
#define YES {cout << "YES\n"; return;}
#define NO {cout << "NO\n"; return;}
#define MUN {cout << "-1\n"; return;}
using namespace std;

const int MODE = 998244353;


void solve(ll tc) {
    ll n, m;

    cin >> n >> m;

    vi X(n + 1), Y(m);

    for (int i = 1; i <= n; i++)
    {
        cin >> X[i];
        X[i] += X[i-1];
    }
    for (int i = 0; i < m; i++)
    {
        cin >> Y[i];
    }
    
    bool istr = 0;
    vi vis(1 << m);
    vis[0] = 1;

    for (int i = 1; i < (1<<m); i++)
    {
        ll summ = 0;
        for (int j = 0; j < m; j++)
            if (i & (1 << j)) summ += Y[j];
        for (int j = 0; j < m; j++)
            if (i & (1 << j)) {
                ll sub = (i ^ (1 << j));
                if (!vis[sub]) continue;
                ll l = upper_bound(all(X), summ-Y[j]) - X.begin();
                ll r = lower_bound(all(X), summ) - X.begin();
                if (r == l) vis[i] = 1;
            }
        if (summ == X[n] && vis[i]) istr = 1;
    }
    

    if (istr) YES;
    NO;
}
 
int32_t main()
{
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int size = 1;   

    // freopen("disrupt.in", "r", stdin   );
    // freopen("disrupt.out", "w", stdout);
    // cin >> size;
    for (int tc = 1; tc <= size; tc++){
        solve(tc);
       // if (tc != size) cout << '\n';
    }
}

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