oj.uz

답안 #972588

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
972588 2024-04-30T16:37:01 Z kfhjad 은행 (IZhO14_bank) C++17
19 / 100
 69 ms 8580 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int dp[1 << 20][2]; // upto person, sum
int people[20], notes[20];

int main()
{
    cin.tie(NULL) -> sync_with_stdio(false);
    int N, M;
    cin >> N >> M;

    for (int i = 0; i < N; ++i)
        cin >> people[i];
    
    for (int i = 0; i < M; ++i)
        cin >> notes[i];
    
    int p, sum;
    
    for (int mask = 1; mask < (1 << M); ++mask)
    {
        bool worked = false;

        for (int i = 0; i < M; ++i)
        {
            if (mask & (1 << i))
            {
                if (dp[mask ^ (1 << i)][0] == -1)
                    continue;
                
                p = dp[mask ^ (1 << i)][0];
                sum = dp[mask ^ (1 << i)][1];

                if (sum + notes[i] < people[p])
                {
                    dp[mask][1] = sum + notes[i];
                    worked = true;
                    break;
                }
                else if (sum + notes[i] == people[p])
                {
                    dp[mask][0] = p + 1;
                    dp[mask][1] = 0;
                    worked = true;

                    if (dp[mask][0] == N)
                    {
                        cout << "YES\n";
                        return 0;
                    }
                }
            }
        }

        if (!worked)
            dp[mask][0] = -1;
    }

    cout << "NO\n";
    
    return 0;
}

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 69 ms 8532 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 6 ms 8580 KB Output is correct

Subtask #2
0 / 25.0

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

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 344 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 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 69 ms 8532 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 6 ms 8580 KB Output is correct
10 Incorrect 0 ms 348 KB Output isn't correct
11 Halted 0 ms 0 KB -