oj.uz

답안 #978955

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
978955 2024-05-10T04:43:04 Z Ska 은행 (IZhO14_bank) C++14
0 / 100
 1 ms 348 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 20;

int n, m;
int a[N], b[N];
// pair<int, int> f[1 << N];

bool backtrack(int mask, int idx, int sum, int lb, int ub) {
    if (idx == n) {
        return true;
    }
    bool first = false;
    for (int i = lb; i < ub; ++i) {
        if ((mask >> i & 1) == 0) {
            continue;
        }
        if (!first) {
            first = true;
            lb = i;
        }
        if (sum + b[i] < a[idx] && backtrack(mask | 1 << i, idx, sum + b[i], lb + (i == lb), ub - (i == ub - 1))) {
            return true;
        }
        if (sum + b[i] == a[idx] && backtrack(mask | 1 << i, idx + 1, 0, lb + (i == lb), ub - (i == ub - 1))) {
            return true;
        }
    }
    return false;
}

// void solve() {
//     for (int mask = 1; mask <= 1 << m; ++mask) {
//         bool ok = false;
//         for (int i = 0; i < m; ++i) {
//             if ((mask >> i & 1) == 0) {
//                 continue;
//             }
//             int prev = mask ^ 1 << i;
//             if (f[prev].first == -1) {
//                 continue;
//             }
//             if (f[prev].second + b[i] < a[f[prev].first]) {
//                 f[mask] = {f[prev].first, f[prev].second + b[i]};
//                 ok = true;
//                 break;
//             } else if (f[prev].second + b[i] == a[f[prev].first]) {
//                 f[mask] = {f[prev].first + 1, 0};
//                 if (f[mask].first == n) {
//                     cout << "YES\n";
//                     return;
//                 }
//                 ok = true;
//                 break;
//             }
//         }
//         if (!ok) {
//             f[mask].first = -1;
//         }
//     }
//     cout << "NO\n";
// }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < m; ++i) {
        cin >> b[i];
    }
    // solve();
    if (backtrack(0, 1, 0, 0, m)) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}

Subtask #1
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -