Submission #1111319

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111319		jobseeker	Bank (IZhO14_bank)	C++17	100 / 100	125 ms	8760 KiB

bank

#include "assert.h"
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <cstring>
#include <fstream>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

// #include <math.h>
// #include <bits/stdc++.h>
// clang-format off
using namespace std;

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// template <class T>
// using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// //map
// tree <int, int, less<int>, rb_tree_tag, tree_order_statistics_node_update> m;
// //multiset
// tree <pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> s;
// s.find_by_order();
// s.order_of_key(); //#strictly smaller.

template <typename T> ostream& operator<<(ostream& out, const vector<T>& vec) {
    if (vec.empty()) { out << "[]"; return out; } out << '[';
    for (int i = 0; i < vec.size() - 1; i++) { out << vec[i] << ", "; }
    return out << vec.back() << ']'; }
template <typename T, size_t size> ostream& operator<<(ostream& out, const array<T, size>& vec) {
    if (vec.empty()) { out << "{}"; return out; } out << '{';
    for (int i = 0; i < vec.size() - 1; i++) { out << vec[i] << ", "; }
    return out << vec.back() << '}'; }
template <typename T> ostream& operator<<(ostream& out, const set<T>& set) {
    out << '{'; for (auto it = set.begin(); it != set.end(); it++) { 
        T element = *it; out << element; if (std::next(it) != set.end()) {out << ", ";} }
    return out << '}'; }
template <typename T> istream &operator>>(istream &in, vector<T> &a) {
    for (int i = 0; i < a.size(); ++i) {
        in >> a[i];
    } return in; }
template <typename T> T min(vector<T> &a) {
    T ans = a[0];
    for (int i = 1; i < a.size(); ++i) { if (a[i] < ans) { ans = a[i]; } } return ans; }
template <typename T> T max(vector<T> &a) {
    T ans = a[0];
    for (int i = 1; i < a.size(); ++i) { if (a[i] > ans) { ans = a[i]; } } return ans; }
    
#define FOR3(i, a, b) for (int i=(a); i<=(signed)(b); i++)
#define FOR2(i, a) for (int i=0; i<(signed)(a); i++)
#define GET_MACRO2(_1,_2,_3,NAME,...) NAME
#define FOR(...) GET_MACRO2(__VA_ARGS__, FOR3, FOR2)(__VA_ARGS__)
#define RFOR(i, b, a) for (int i=(b); i>=(signed)(a); i--)

#define dbg1(v) cerr << "L" << __LINE__ << "> " << #v << "=" << (v) << endl;
#define dbg2(x,y) cerr << "L" << __LINE__ << "> " << #x << "=" << (x) << ", " << #y << "=" << (y) << endl;
#define dbg3(x,y,z) cerr << "L" << __LINE__ << "> " << #x << "=" << (x) << ", " << #y << "=" << (y) << ", " << #z << "=" << (z) << endl;
#define dbg4(x,y,z,w) cerr << "L" << __LINE__ << "> " << #x << "=" << (x) << ", " << #y << "=" << (y) << ", " << #z << "=" << (z) << ", " << #w << "=" << (w) << endl;
#define GET_MACRO(_1,_2,_3,_4,NAME,...) NAME
#define dbg(...) GET_MACRO(__VA_ARGS__, dbg4, dbg3, dbg2, dbg1)(__VA_ARGS__)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
#define ll long long
#define ar array
#define nl "\n"
using vi = vector<int>;
using vll = vector<ll>;
using ii = ar<int, 2>;
// clang-format on

// #ifdef LOCAL
// #include "algo/debug.h"
// #else
// #define debug(...) 42
// #endif

const int M = 1e9 + 7;
const int INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 2;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
const char dir[4] = {'U', 'R', 'D', 'L'};

int main() {
    // freopen("exercise.in", "r", stdin);
    // freopen("exercise.out", "w", stdout);
    //	ifstream in("/Users/a/Downloads/test_input.txt");
    //	cin.rdbuf(in.rdbuf());
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    vi sz(n), w(m);
    cin >> sz;
    cin >> w;

    bool found = false;
    vector<ar<int, 2>> d(1 << m, {0, 0});
    FOR(mask, (1 << m)) {
        FOR(j, m) {
            if (mask & (1 << j)) {
                auto [a, b] = d[mask ^ (1 << j)];
                if (w[j] + b < sz[a]) {
                    chmax(d[mask], {a, b + w[j]});
                } else if (w[j] + b == sz[a]) {
                    chmax(d[mask], {a + 1, 0});
                    if (a + 1 == n) {
                        found = true;
                        // dbg(mask);
                        break;
                    }
                }
                // dbg(mask, j, d[mask]);
            }
        }
        if (found) {
            break;
        }
    }
    if (found) {
        cout << "YES";
    } else {
        cout << "NO";
    }
    // auto t = d[(1 << n) - 1];
    // int ans = t.ride;
    // if (t.extra > 0) {
    //     ans++;
    // }
    // cout << ans;
}

Compilation message (stderr)

bank.cpp: In instantiation of 'std::istream& operator>>(std::istream&, std::vector<_Tp>&) [with T = int; std::istream = std::basic_istream<char>]':
bank.cpp:106:12:   required from here
bank.cpp:50:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for (int i = 0; i < a.size(); ++i) {
      |                     ~~^~~~~~~~~~

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