제출 #1248891

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1248891		kitsune	은행 (IZhO14_bank)	C++20	100 / 100	147 ms	9664 KiB

bank

#include <bits/stdc++.h>
/// kitsune
using namespace std;

#define fi first
#define se second
#define mp make_pair
//#define int long long
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define rep(i, l, r) for (int i = (int)(l); i <= (int)(r); i++)
#define per(i, r, l) for (int i = (int)(r); i >= (int)(l); i--)

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template<typename _Tp> bool minimize(_Tp& __a, const _Tp& __b) { if (__a > __b) { __a = __b; return true; } return false; }
template<typename _Tp> bool maximize(_Tp& __a, const _Tp& __b) { if (__a < __b) { __a = __b; return true; } return false; }

const int siz = 1e5 + 2;
const int SIZ = 1e6 + 2;
const int mod = 1e9 + 7;
const int maxx = 2e9;
const ll MAXX = 1e18;
const string file = "1";

int n, m;
int a[20], b[20];
int s[1 << 20], p[1 << 20];
//bool f[1 << 20]; bool g[1 << 20];
//
//bool dp(int mask) {
//    int pos = p[mask];
//
//    if (pos == n) {
//        return true;
//    }
//
//    bool& res = f[mask];
//    bool& cal = g[mask];
//
//    if (cal) {
//        return res;
//    }
//
//    res = false;
//    rep (i, 0, m - 1) {
//        if (mask & (1 << i)) {
//            continue;
//        }
//
//        int new_mask = mask ^ (1 << i);
//        int sum = s[new_mask];
//        if (sum <= a[pos]) {
//            res |= dp(new_mask);
//        }
//    }
//
//    cal = true;
//    return res;
//}

bool dp[1 << 20];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (fopen((file + ".inp").c_str(), "r")) {
        freopen((file + ".inp").c_str(), "r", stdin);
        freopen((file + ".out").c_str(), "w", stdout);
    }

    cin >> n >> m;

    rep (i, 0, n - 1) {
        cin >> a[i];

        a[i] += (i == 0 ? 0 : a[i - 1]);
    }

    rep (i, 0, m - 1) {
        cin >> b[i];
    }

    rep (mask, 0, (1 << m) - 1) {
        rep (i, 0, m - 1) {
            if (mask & (1 << i)) {
                s[mask] += b[i];
            }
        }

        p[mask] = upper_bound(a, a + n, s[mask]) - a;
    }

    per (mask, (1 << m) - 1, 0) {
        int pos = p[mask];

        if (pos == n) {
            dp[mask] = true;
            continue;
        }

        dp[mask] = false;
        rep (i, 0, m - 1) {
            if (mask & (1 << i)) {
                continue;
            }

            int new_mask = mask ^ (1 << i);
            int sum = s[new_mask];
            if (sum <= a[pos]) {
                dp[mask] |= dp[new_mask];
            }
        }
    }

    cout << (dp[0] ? "YES" : "NO") << "\n";

//    cerr << "Time: " << 1000 * clock() / CLOCKS_PER_SEC << " ms\n";

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

bank.cpp: In function 'int main()':
bank.cpp:71:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         freopen((file + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bank.cpp:72:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         freopen((file + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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