oj.uz

Submission #495502

# Submission time Handle Problem Language Result Execution time Memory
495502 2021-12-19T05:33:10 Z adhitya Bank (IZhO14_bank) C++14
100 / 100
 125 ms 4396 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;
int n,m;
vector<int> salary,coin;
int solve(int mask,int index,int curwt,vector<int>& dp){
    if(index==n)   return 1;
    if(dp[mask]!=-1)    return dp[mask];
    dp[mask] = 0;
    for(int i=0;i<m;i++){
        if((mask & (1<<i)) == 0){
            // ith coin can be used
            if(salary[index] > curwt + coin[i]){
                dp[mask] = max(dp[mask],solve(mask|(1<<i),index,curwt+coin[i],dp));
                if(dp[mask]==1)    break;
            }else if(salary[index]==curwt+coin[i]){
                dp[mask] = max(dp[mask], solve(mask|(1<<i),index+1,curwt+coin[i],dp));
                if(dp[mask]==1)    break;
            }
        }
    }
    return dp[mask];
    
}
int main(){
    cin >> n >> m;
    salary.resize(n);
    for(int i=0;i<n;i++){
        cin >> salary[i];
    }
    coin.resize(m);
    for(int i=0;i<m;i++){
        cin >> coin[i];
    }
    for(int i=1;i<n;i++){
        salary[i] += salary[i-1];
    }
    vector<int> dp(1<<m,-1);
    solve(0,0,0,dp);
    // dp[mask] => whether we can pay remaining person with unset bits of coins where remaining person is specified by the sum of used coins
    if(dp[0])   cout<<"YES\n";
    else    cout<<"NO\n";
    
    return 0;
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 416 KB Output is correct
5 Correct 2 ms 4392 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 2 ms 4388 KB Output is correct
9 Correct 123 ms 4388 KB Output is correct

Subtask #2
25.0 / 25.0

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

Subtask #3
27.0 / 27.0

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

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 416 KB Output is correct
5 Correct 2 ms 4392 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 2 ms 4388 KB Output is correct
9 Correct 123 ms 4388 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 0 ms 332 KB Output is correct
22 Correct 0 ms 332 KB Output is correct
23 Correct 1 ms 292 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 0 ms 332 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 0 ms 332 KB Output is correct
29 Correct 0 ms 332 KB Output is correct
30 Correct 2 ms 332 KB Output is correct
31 Correct 2 ms 4300 KB Output is correct
32 Correct 2 ms 4300 KB Output is correct
33 Correct 3 ms 4300 KB Output is correct
34 Correct 2 ms 4300 KB Output is correct
35 Correct 2 ms 4300 KB Output is correct
36 Correct 2 ms 4384 KB Output is correct
37 Correct 3 ms 4300 KB Output is correct
38 Correct 2 ms 4300 KB Output is correct
39 Correct 2 ms 4352 KB Output is correct
40 Correct 2 ms 4308 KB Output is correct
41 Correct 2 ms 4300 KB Output is correct
42 Correct 62 ms 4396 KB Output is correct
43 Correct 4 ms 4300 KB Output is correct
44 Correct 2 ms 4300 KB Output is correct
45 Correct 2 ms 4300 KB Output is correct
46 Correct 3 ms 4392 KB Output is correct
47 Correct 2 ms 4300 KB Output is correct
48 Correct 2 ms 4300 KB Output is correct
49 Correct 2 ms 4392 KB Output is correct
50 Correct 2 ms 4300 KB Output is correct
51 Correct 3 ms 4300 KB Output is correct
52 Correct 3 ms 4300 KB Output is correct
53 Correct 2 ms 4300 KB Output is correct
54 Correct 2 ms 4300 KB Output is correct
55 Correct 2 ms 4300 KB Output is correct
56 Correct 2 ms 4300 KB Output is correct
57 Correct 125 ms 4396 KB Output is correct
58 Correct 2 ms 4300 KB Output is correct