oj.uz

Submission #671846

# Submission time Handle Problem Language Result Execution time Memory
671846 2022-12-14T04:49:36 Z moday_morning Bank (IZhO14_bank) C++17
71 / 100
 1000 ms 186104 KB 
#include <bits/stdc++.h>
#define int long long
#define fr first
#define sc second
#define pb push_back
using namespace std;

int n, m;
int a[20], b[20], sum[20], s[1 << 20];
bool c[1 << 20][21];
vector <int> v[1<<20];
 
void update (int i, int j) {
    if (c[i][j]) {
        return;
    }
    c[i][j]=true;
    for (auto x : v[i]) {
        update((i | (1 << x)), j);
    }
}
void solve() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (i > 0) {
            sum[i] = sum[i-1];
        }
        sum[i] += a[i];
    }
    for (int j = 0; j < m; j++) {
        cin >> b[j];
    }
    for (int i = 0; i < (1 << m); i++) {
        for (int j = 0; j < m; j++) {
            if (i & (1 << j)) {
                s[i] += b[j];
            }
            else {
                v[i].push_back(j);
            }
        }
    }
    update(0, 0);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < (1 << m); j++) {
            int x = 0;
            if (i > 0) {
                x = sum[i-1];
            }
            if (c[j][i] && s[j] - x == a[i]) {
                update(j, i+1);
            }
            else {
                c[j][i]=false;
            }
        }
    }
    for (int j = 0; j < (1 << m); j++) {
        if (c[j][n]) {
            cout << "YES\n";
            return;
        }
    }
    cout << "NO\n";
}

signed main() {
//    usaco("triangles");
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24916 KB Output is correct
2 Correct 14 ms 24864 KB Output is correct
3 Correct 13 ms 25056 KB Output is correct
4 Correct 28 ms 28968 KB Output is correct
5 Correct 615 ms 186104 KB Output is correct
6 Correct 13 ms 25044 KB Output is correct
7 Correct 13 ms 25044 KB Output is correct
8 Correct 713 ms 185892 KB Output is correct
9 Correct 606 ms 185872 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 25044 KB Output is correct
2 Correct 14 ms 25056 KB Output is correct
3 Correct 13 ms 25044 KB Output is correct
4 Correct 13 ms 25044 KB Output is correct
5 Correct 13 ms 24988 KB Output is correct
6 Correct 13 ms 25044 KB Output is correct
7 Correct 13 ms 24948 KB Output is correct
8 Correct 13 ms 25028 KB Output is correct
9 Correct 13 ms 25044 KB Output is correct
10 Correct 13 ms 25044 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 26836 KB Output is correct
2 Correct 19 ms 26872 KB Output is correct
3 Correct 19 ms 26780 KB Output is correct
4 Correct 18 ms 26800 KB Output is correct
5 Correct 18 ms 26876 KB Output is correct
6 Correct 18 ms 26836 KB Output is correct
7 Correct 18 ms 26836 KB Output is correct
8 Correct 17 ms 26836 KB Output is correct
9 Correct 18 ms 26800 KB Output is correct
10 Correct 17 ms 26836 KB Output is correct
11 Correct 18 ms 26836 KB Output is correct

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24916 KB Output is correct
2 Correct 14 ms 24864 KB Output is correct
3 Correct 13 ms 25056 KB Output is correct
4 Correct 28 ms 28968 KB Output is correct
5 Correct 615 ms 186104 KB Output is correct
6 Correct 13 ms 25044 KB Output is correct
7 Correct 13 ms 25044 KB Output is correct
8 Correct 713 ms 185892 KB Output is correct
9 Correct 606 ms 185872 KB Output is correct
10 Correct 12 ms 25044 KB Output is correct
11 Correct 14 ms 25056 KB Output is correct
12 Correct 13 ms 25044 KB Output is correct
13 Correct 13 ms 25044 KB Output is correct
14 Correct 13 ms 24988 KB Output is correct
15 Correct 13 ms 25044 KB Output is correct
16 Correct 13 ms 24948 KB Output is correct
17 Correct 13 ms 25028 KB Output is correct
18 Correct 13 ms 25044 KB Output is correct
19 Correct 13 ms 25044 KB Output is correct
20 Correct 17 ms 26836 KB Output is correct
21 Correct 19 ms 26872 KB Output is correct
22 Correct 19 ms 26780 KB Output is correct
23 Correct 18 ms 26800 KB Output is correct
24 Correct 18 ms 26876 KB Output is correct
25 Correct 18 ms 26836 KB Output is correct
26 Correct 18 ms 26836 KB Output is correct
27 Correct 17 ms 26836 KB Output is correct
28 Correct 18 ms 26800 KB Output is correct
29 Correct 17 ms 26836 KB Output is correct
30 Correct 18 ms 26836 KB Output is correct
31 Correct 688 ms 185848 KB Output is correct
32 Correct 753 ms 185864 KB Output is correct
33 Correct 949 ms 185864 KB Output is correct
34 Correct 972 ms 185824 KB Output is correct
35 Correct 895 ms 185932 KB Output is correct
36 Correct 913 ms 185860 KB Output is correct
37 Correct 683 ms 185804 KB Output is correct
38 Correct 644 ms 185864 KB Output is correct
39 Execution timed out 1090 ms 185804 KB Time limit exceeded
40 Halted 0 ms 0 KB -