oj.uz

Submission #760994

# Submission time Handle Problem Language Result Execution time Memory
760994 2023-06-19T01:52:33 Z normankr07 Bank (IZhO14_bank) C++14
100 / 100
 109 ms 16740 KB 
/*
Templete by norman/KNN-07
Who tf even love CP :sob:
*/
#include <bits/stdc++.h>

// Wish you can debug? YesYes
#ifndef LOCAL
#define cerr \
    if (0)   \
    cerr
#endif

// Policy based DS?
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

// Who tf deal with overflow
// #define int long long

// Judges with GCC >= 12 only needs Ofast
// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
// #pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("arch=skylake")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
using namespace std;

#define el '\n'
#define mpp make_pair
#define pb push_back
#define ppb pop_back
#define pf push_front
#define emp emplace_back
#define fi first
#define nd second
#define forinc(i, a, b) for (int i = (a); i <= (b); i++)
#define fordec(i, a, b) for (int i = (a); i >= (b); i--)
#define alle(x) (x).begin(), (x).end()
#define ralle(x) (x).rbegin(), (x).rend()
#define mms(a, v) memset(a, v, sizeof(a))
#define lwb(a, v) lower_bound((a).begin(), (a).end(), v)
#define upb(a, v) upper_bound((a).begin(), (a).end(), v)
#define bit(i, a) (((a) >> (i)) & 1)

#define BIT_SET(a, b) ((a) |= (1ULL << (b)))
#define BIT_CLEAR(a, b) ((a) &= ~(1ULL << (b)))
#define BIT_FLIP(a, b) ((a) ^= (1ULL << (b)))
#define BIT_CHECK(a, b) (!!((a) & (1ULL << (b))))
#define BITMASK_SET(x, mask) ((x) |= (mask))
#define BITMASK_CLEAR(x, mask) ((x) &= (~(mask)))
#define BITMASK_FLIP(x, mask) ((x) ^= (mask))
#define BITMASK_CHECK_ALL(x, mask) (!(~(x) & (mask)))
#define BITMASK_CHECK_ANY(x, mask) ((x) & (mask))
#define POPCNT(mask) __builtin_popcount(mask)
#define POPCNTLL(mask) __builtin_popcountll(mask)
#define CTZ(mask) __builtin_ctz(mask)
#define CTZLL(mask) __builtin_ctzll(mask)

typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef map<int, int> mii;
typedef map<ll, ll> mll;
typedef vector<bool> vb;

template <typename T, typename U>
inline void maximize(T &x, U y)
{
    if (y < x)
        x = y;
}
template <typename T, typename U>
inline void minimize(T &x, U y)
{
    if (x < y)
        x = y;
}
inline int add_m(int a, int b, int mod)
{
    int res = a + b;
    return (res >= mod ? res - mod : res);
}
inline int mod_neg(int a, int b, int mod)
{
    int res;
    if (abs(a - b) < mod)
        res = a - b;
    else
        res = (a - b) % mod;
    return (res < 0 ? res + mod : res);
}
inline int mul_wmod(int a, int b, int c)
{
    ll res = (ll)a * b;
    return (res >= c ? res % c : res);
}
inline int mul_wnmod(int a, int b, int c)
{
    ll res = (ll)a * b;
    return ((res % c) + c) % c;
}

// Debugger Utils
template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }

template <size_t i, class T>
ostream &print_tuple_utils(ostream &out, const T &tup)
{
    if constexpr (i == tuple_size<T>::value)
        return out << ")";
    else
        return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup);
}
template <class... U>
ostream &operator<<(ostream &out, const tuple<U...> &t)
{
    return print_tuple_utils<0, tuple<U...>>(out, t);
}
#define db(val) "[" #val " = " << (val) << "] "
// End if debugger utils

namespace Hasher
{
    struct custom_hash
    {
        static uint32_t splitmix64(uint32_t x)
        {
            x += 0x9e3779b97f4a7c15;
            x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
            x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
            return x ^ (x >> 31);
        }
        size_t operator()(uint64_t x) const
        {
            static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
            return splitmix64(x + FIXED_RANDOM);
        }
    };
    struct hash_pair
    {
        template <class T1, class T2>
        size_t operator()(const pair<T1, T2> &p) const
        {
            auto hash1 = custom_hash{}(p.first);
            auto hash2 = custom_hash{}(p.second);
            if (hash1 != hash2)
                return hash1 ^ hash2;
            return hash1;
        }
    };
    struct hash_pair_pair
    {
        template <class T1, class T2>
        size_t operator()(const pair<T1, T2> &p) const
        {
            auto hash1 = custom_hash{}(p.first);
            auto hash2 = hash_pair{}(p.second);
            if (hash1 != hash2)
                return hash1 ^ hash2;
            return hash1;
        }
    };
}
using namespace Hasher;

const string taskname = "";
const bool tc = false;

const int oo = 1e9, mod = 1e9 + 7;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll ool = 1e18;
const ldb eps = 1e-6;
const int MAXN = 1e6;

/*
Author: normankr07
Problem: IZHO14_BANK

Submission links:
    - https://oj.uz/problem/view/IZhO14_bank?locale=en

Editorial links:
    - not exist

Algorithm:
*/

pll dp[(1 << 21)];
ll a[MAXN], b[MAXN];
void solve()
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < m; i++)
        cin >> b[i];
    sort(a, a + n);
    sort(b, b + m);
    bool can = 0;
    // mms(dp, 0);
    for (int mask = 1; mask < (1 << m) && can == 0; mask++)
    {
        forinc(i, 0, m - 1)
        {
            int newmask = mask;
            BIT_FLIP(newmask, i);
            if (!BIT_CHECK(mask, i) || dp[mask].fi > dp[newmask].fi)
                continue;
            auto &cur = dp[newmask];
            // cur.fi = max(cur.fi, dp[mask].fi);
            if (cur.first > dp[mask].first) dp[mask] = cur;
            if (a[cur.fi] >= b[i] + cur.nd && dp[mask].nd < b[i] + cur.nd)
                dp[mask].nd = b[i] + cur.nd;
        }
        if (dp[mask].nd == a[dp[mask].fi])
            dp[mask] = {dp[mask].fi + 1, 0};
        can = can || (dp[mask].fi == n);
    }
    cout << (can ? "YES" : "NO");
}

int32_t main()
{
    if (fopen((taskname + ".inp").c_str(), "r"))
    {
        freopen((taskname + ".inp").c_str(), "r", stdin);
        freopen((taskname + ".out").c_str(), "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int tsc = 1;
    if (tc)
    {
        cin >> tsc;
    }
    while (tsc--)
    {
        solve();
        cout << el;
    }
#ifdef LOCAL
    cerr << "\n"
         << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
}

Compilation message

bank.cpp: In function 'std::ostream& print_tuple_utils(std::ostream&, const T&)':
bank.cpp:123:8: warning: 'if constexpr' only available with '-std=c++17' or '-std=gnu++17'
  123 |     if constexpr (i == tuple_size<T>::value)
      |        ^~~~~~~~~
bank.cpp: In function 'int32_t main()':
bank.cpp:241:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  241 |         freopen((taskname + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bank.cpp:242:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  242 |         freopen((taskname + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 86 ms 16708 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 88 ms 16720 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 2 ms 472 KB Output is correct
11 Correct 2 ms 596 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 86 ms 16708 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 88 ms 16720 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 2 ms 596 KB Output is correct
21 Correct 2 ms 468 KB Output is correct
22 Correct 2 ms 596 KB Output is correct
23 Correct 2 ms 596 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 2 ms 596 KB Output is correct
26 Correct 2 ms 596 KB Output is correct
27 Correct 1 ms 468 KB Output is correct
28 Correct 2 ms 468 KB Output is correct
29 Correct 2 ms 472 KB Output is correct
30 Correct 2 ms 596 KB Output is correct
31 Correct 89 ms 16704 KB Output is correct
32 Correct 90 ms 16688 KB Output is correct
33 Correct 109 ms 16624 KB Output is correct
34 Correct 100 ms 16616 KB Output is correct
35 Correct 103 ms 16660 KB Output is correct
36 Correct 86 ms 16712 KB Output is correct
37 Correct 92 ms 16644 KB Output is correct
38 Correct 90 ms 16716 KB Output is correct
39 Correct 1 ms 340 KB Output is correct
40 Correct 75 ms 344 KB Output is correct
41 Correct 86 ms 16736 KB Output is correct
42 Correct 100 ms 16624 KB Output is correct
43 Correct 96 ms 16624 KB Output is correct
44 Correct 101 ms 16696 KB Output is correct
45 Correct 9 ms 1864 KB Output is correct
46 Correct 100 ms 16732 KB Output is correct
47 Correct 89 ms 16740 KB Output is correct
48 Correct 1 ms 340 KB Output is correct
49 Correct 86 ms 16716 KB Output is correct
50 Correct 88 ms 16632 KB Output is correct
51 Correct 104 ms 16716 KB Output is correct
52 Correct 99 ms 16728 KB Output is correct
53 Correct 91 ms 16676 KB Output is correct
54 Correct 87 ms 16696 KB Output is correct
55 Correct 89 ms 16692 KB Output is correct
56 Correct 89 ms 16664 KB Output is correct
57 Correct 91 ms 16708 KB Output is correct
58 Correct 90 ms 16700 KB Output is correct