oj.uz

Submission #285303

# Submission time Handle Problem Language Result Execution time Memory
285303 2020-08-28T16:17:20 Z BeanZ Bank (IZhO14_bank) C++14
52 / 100
 1000 ms 20344 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define endl '\n'

const int N = 2e5 + 5;
const int mod = 1e9 + 7;
vector<ll> choice[1005];
ll a[25], b[25], dp[2000006];
int main(){
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        if (fopen("VietCT.INP", "r")){
                freopen("VietCT.INP", "r", stdin);
                freopen("VietCT.OUT", "w", stdout);
        }
        ll 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];
        for (int i = 1; i < (1 << m); i++){
                ll cost = 0;
                for (int j = 0; j < m; j++){
                        if (i & (1 << j)){
                                cost += b[j];
                        }
                }
                if (cost <= 1000) choice[cost].push_back(i);
        }
        for (int i = 1; i < (1 << m); i++) dp[i] = -2;
        dp[0] = -1;
        bool flag = false;
        for (int i = 0; i < n; i++){
                for (int j = 1; j < (1 << m); j++){
                        if (choice[a[i]].size() == 0) continue;
                        for (auto k : choice[a[i]]){
                                if ((j & k) == k){
                                        if (dp[j ^ k] == (i - 1)){
                                                dp[j] = i;
                                        }
                                }
                        }
                        //cout << dp[j] << " " << j << endl;
                        if (dp[j] == (n - 1)) flag = true;
                }
        }
        if (flag) cout << "YES";
        else cout << "NO";
}
/*
*/

Compilation message

bank.cpp: In function 'int main()':
bank.cpp:16:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   16 |                 freopen("VietCT.INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
bank.cpp:17:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   17 |                 freopen("VietCT.OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 11 ms 1024 KB Output is correct
5 Correct 86 ms 20344 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Execution timed out 1089 ms 19192 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

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

Subtask #3
27.0 / 27.0

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

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 11 ms 1024 KB Output is correct
5 Correct 86 ms 20344 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Execution timed out 1089 ms 19192 KB Time limit exceeded
9 Halted 0 ms 0 KB -