Submission #477794

#	Time	Username	Problem	Language	Result	Execution time	Memory
477794		__SIGSEGV__	Bank (IZhO14_bank)	C++17	100 / 100	130 ms	8648 KiB

bank

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <chrono>
#include <algorithm>
#include <stdio.h>
#include <unordered_set>
#include <bitset>
#include <cstring>
#include <cmath>
#include <climits>
#include <cassert>
#include <ctime>
#include <unistd.h>
 
using namespace std;
 
#define rep(x, a, b) for (int x = (int) (a); x < (int) (b); x++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int) (x).size()
#define fi first
#define se second
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
 
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#ifdef DEBUG
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
 
template<typename T> bool ckmin(T& a, T b) { return (a > b ? (a = b, false) : true); }
template<typename T> bool ckmax(T& a, T b) { return (a < b ? (a = b, false) : true); }
 
void solve(const int& test_number) {
    int n, m; cin >> n >> m;
    vector<int> customers(n), notes(m);
    rep(i, 0, n) cin >> customers[i];
    rep(i, 0, m) cin >> notes[i];

    vector<int> covered((1 << m), -1); // max pefix of people covered using subset s
    vector<int> remaining_pile((1 << m), -1); // amount remaining after covering some prefix

    covered[0] = 0;
    remaining_pile[0] = 0;
    bool done = false;

    rep(mask, 1, (1 << m)) {
        rep(i, 0, m) {
            if (!(mask & (1 << i))) continue;
            int prev = mask ^ (1 << i);
            if (covered[prev] == -1) continue;

            int total_rem = notes[i] + remaining_pile[prev];
            int target = customers[covered[prev]];

            if (total_rem < target) {
                covered[mask] = covered[prev];
                remaining_pile[mask] = total_rem;
            }
            else if (total_rem == target) {
                covered[mask] = covered[prev] + 1;
                remaining_pile[mask] = 0;
            }
        }   
        if (covered[mask] == n) done = true;
    }
    cout << (done ? "YES" : "NO") << '\n';
}   
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.precision(10);
    cout << fixed;
 
    int tt = 1;
//    cin >> tt;
 
#ifdef LOCAL_DEFINE
    auto start = std::chrono::high_resolution_clock::now();
#endif    
 
    rep(t, 0, tt) 
        solve(t + 1);
 
#ifdef LOCAL_DEFINE
    auto stop = std::chrono::high_resolution_clock::now();
    auto elapsed_ticks = std::chrono::duration_cast<std::chrono::milliseconds>(stop - start);
 
    std::cerr << "Execution Completed in: " << elapsed_ticks.count() << " milliseconds\n";
#endif
    return 0;
}

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