oj.uz

Submission #566289

# Submission time Handle Problem Language Result Execution time Memory
566289 2022-05-22T08:15:40 Z shrimb Bootfall (IZhO17_bootfall) C++17
28 / 100
 1000 ms 156808 KB 
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx,avx2,fma")

#include"bits/stdc++.h"
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<class x>
using ordered_set = tree<x, null_type,less<x>, rb_tree_tag,tree_order_statistics_node_update>;

// #define int long long
#define endl '\n'
#define mod 1000000007
//\
#define mod 1686876991

const int maxn = 271;

vector<vector<int>> dp0(maxn, vector<int>(maxn*maxn)), dp1(maxn, vector<int>(maxn*maxn));
bitset<maxn*maxn> ans;
int n, tot, ex=-1, total;
int a[maxn];

void rec () {
    for (int i = n ; i >= 0 ; i--) {
        for (ex = 0 ; ex <= n ; ex++) {
            for (int j = 0 ; j <= total ; j++) {
                if (i == n) dp0[ex][j] = j == 0;
                else if (i == ex) dp0[ex][j] = dp1[ex][j];
                else dp0[ex][j] = dp1[ex][j] || (j - a[i] < 0 ? 0 : dp1[ex][j - a[i]]);
            }
        }
        swap(dp0, dp1);
    }
    swap(dp0, dp1);
}

signed main () {
    cin.tie(0)->sync_with_stdio(0);

    cin >> n;
    for (int i = 0 ; i < n ; i++) cin >> a[i], total += a[i];
    for (int i = 0 ; i <= total ; i++) ans[i] = 1;
    rec();
    if (!dp0[n][total/2]) {
        cout << 0 << endl;
        return 0;
    }
    // cerr << "here\n";
    ans[0] = 0;
    for (int i = 0 ; i < n ; i++) {
        tot = total - a[i];
        ex = i;
        for (int j = 1 ; j <= total ; j++) {
            if ((tot+j)&1||!dp0[i][(tot+j)/2]) {
                ans[j] = 0;
            }
        }
    }
    cout << ans.count() << endl;
    for (int i = 0 ; i <= total ; i++) if (ans[i]) cout << i << " ";
}

Compilation message

bootfall.cpp:17:1: warning: multi-line comment [-Wcomment]
   17 | //\
      | ^

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 156588 KB Output is correct
2 Correct 68 ms 156684 KB Output is correct
3 Correct 62 ms 156620 KB Output is correct
4 Correct 65 ms 156676 KB Output is correct
5 Correct 65 ms 156616 KB Output is correct
6 Correct 64 ms 156624 KB Output is correct
7 Correct 64 ms 156624 KB Output is correct
8 Correct 64 ms 156588 KB Output is correct
9 Correct 63 ms 156576 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 156588 KB Output is correct
2 Correct 68 ms 156684 KB Output is correct
3 Correct 62 ms 156620 KB Output is correct
4 Correct 65 ms 156676 KB Output is correct
5 Correct 65 ms 156616 KB Output is correct
6 Correct 64 ms 156624 KB Output is correct
7 Correct 64 ms 156624 KB Output is correct
8 Correct 64 ms 156588 KB Output is correct
9 Correct 63 ms 156576 KB Output is correct
10 Correct 67 ms 156636 KB Output is correct
11 Correct 67 ms 156652 KB Output is correct
12 Correct 68 ms 156584 KB Output is correct
13 Correct 69 ms 156572 KB Output is correct
14 Correct 68 ms 156568 KB Output is correct
15 Correct 66 ms 156628 KB Output is correct
16 Correct 67 ms 156588 KB Output is correct
17 Correct 67 ms 156628 KB Output is correct
18 Correct 65 ms 156680 KB Output is correct
19 Correct 65 ms 156636 KB Output is correct
20 Correct 74 ms 156620 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 156588 KB Output is correct
2 Correct 68 ms 156684 KB Output is correct
3 Correct 62 ms 156620 KB Output is correct
4 Correct 65 ms 156676 KB Output is correct
5 Correct 65 ms 156616 KB Output is correct
6 Correct 64 ms 156624 KB Output is correct
7 Correct 64 ms 156624 KB Output is correct
8 Correct 64 ms 156588 KB Output is correct
9 Correct 63 ms 156576 KB Output is correct
10 Correct 67 ms 156636 KB Output is correct
11 Correct 67 ms 156652 KB Output is correct
12 Correct 68 ms 156584 KB Output is correct
13 Correct 69 ms 156572 KB Output is correct
14 Correct 68 ms 156568 KB Output is correct
15 Correct 66 ms 156628 KB Output is correct
16 Correct 67 ms 156588 KB Output is correct
17 Correct 67 ms 156628 KB Output is correct
18 Correct 65 ms 156680 KB Output is correct
19 Correct 65 ms 156636 KB Output is correct
20 Correct 74 ms 156620 KB Output is correct
21 Correct 143 ms 156584 KB Output is correct
22 Correct 181 ms 156684 KB Output is correct
23 Correct 90 ms 156604 KB Output is correct
24 Correct 303 ms 156808 KB Output is correct
25 Correct 527 ms 156688 KB Output is correct
26 Correct 600 ms 156704 KB Output is correct
27 Correct 572 ms 156712 KB Output is correct
28 Correct 605 ms 156720 KB Output is correct
29 Correct 640 ms 156692 KB Output is correct
30 Correct 380 ms 156720 KB Output is correct
31 Correct 468 ms 156620 KB Output is correct
32 Correct 340 ms 156684 KB Output is correct
33 Correct 651 ms 156688 KB Output is correct
34 Correct 637 ms 156708 KB Output is correct
35 Correct 588 ms 156716 KB Output is correct
36 Correct 338 ms 156688 KB Output is correct

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 156588 KB Output is correct
2 Correct 68 ms 156684 KB Output is correct
3 Correct 62 ms 156620 KB Output is correct
4 Correct 65 ms 156676 KB Output is correct
5 Correct 65 ms 156616 KB Output is correct
6 Correct 64 ms 156624 KB Output is correct
7 Correct 64 ms 156624 KB Output is correct
8 Correct 64 ms 156588 KB Output is correct
9 Correct 63 ms 156576 KB Output is correct
10 Correct 67 ms 156636 KB Output is correct
11 Correct 67 ms 156652 KB Output is correct
12 Correct 68 ms 156584 KB Output is correct
13 Correct 69 ms 156572 KB Output is correct
14 Correct 68 ms 156568 KB Output is correct
15 Correct 66 ms 156628 KB Output is correct
16 Correct 67 ms 156588 KB Output is correct
17 Correct 67 ms 156628 KB Output is correct
18 Correct 65 ms 156680 KB Output is correct
19 Correct 65 ms 156636 KB Output is correct
20 Correct 74 ms 156620 KB Output is correct
21 Correct 143 ms 156584 KB Output is correct
22 Correct 181 ms 156684 KB Output is correct
23 Correct 90 ms 156604 KB Output is correct
24 Correct 303 ms 156808 KB Output is correct
25 Correct 527 ms 156688 KB Output is correct
26 Correct 600 ms 156704 KB Output is correct
27 Correct 572 ms 156712 KB Output is correct
28 Correct 605 ms 156720 KB Output is correct
29 Correct 640 ms 156692 KB Output is correct
30 Correct 380 ms 156720 KB Output is correct
31 Correct 468 ms 156620 KB Output is correct
32 Correct 340 ms 156684 KB Output is correct
33 Correct 651 ms 156688 KB Output is correct
34 Correct 637 ms 156708 KB Output is correct
35 Correct 588 ms 156716 KB Output is correct
36 Correct 338 ms 156688 KB Output is correct
37 Execution timed out 1087 ms 156672 KB Time limit exceeded
38 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 156588 KB Output is correct
2 Correct 68 ms 156684 KB Output is correct
3 Correct 62 ms 156620 KB Output is correct
4 Correct 65 ms 156676 KB Output is correct
5 Correct 65 ms 156616 KB Output is correct
6 Correct 64 ms 156624 KB Output is correct
7 Correct 64 ms 156624 KB Output is correct
8 Correct 64 ms 156588 KB Output is correct
9 Correct 63 ms 156576 KB Output is correct
10 Correct 67 ms 156636 KB Output is correct
11 Correct 67 ms 156652 KB Output is correct
12 Correct 68 ms 156584 KB Output is correct
13 Correct 69 ms 156572 KB Output is correct
14 Correct 68 ms 156568 KB Output is correct
15 Correct 66 ms 156628 KB Output is correct
16 Correct 67 ms 156588 KB Output is correct
17 Correct 67 ms 156628 KB Output is correct
18 Correct 65 ms 156680 KB Output is correct
19 Correct 65 ms 156636 KB Output is correct
20 Correct 74 ms 156620 KB Output is correct
21 Correct 143 ms 156584 KB Output is correct
22 Correct 181 ms 156684 KB Output is correct
23 Correct 90 ms 156604 KB Output is correct
24 Correct 303 ms 156808 KB Output is correct
25 Correct 527 ms 156688 KB Output is correct
26 Correct 600 ms 156704 KB Output is correct
27 Correct 572 ms 156712 KB Output is correct
28 Correct 605 ms 156720 KB Output is correct
29 Correct 640 ms 156692 KB Output is correct
30 Correct 380 ms 156720 KB Output is correct
31 Correct 468 ms 156620 KB Output is correct
32 Correct 340 ms 156684 KB Output is correct
33 Correct 651 ms 156688 KB Output is correct
34 Correct 637 ms 156708 KB Output is correct
35 Correct 588 ms 156716 KB Output is correct
36 Correct 338 ms 156688 KB Output is correct
37 Execution timed out 1087 ms 156672 KB Time limit exceeded
38 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 156588 KB Output is correct
2 Correct 68 ms 156684 KB Output is correct
3 Correct 62 ms 156620 KB Output is correct
4 Correct 65 ms 156676 KB Output is correct
5 Correct 65 ms 156616 KB Output is correct
6 Correct 64 ms 156624 KB Output is correct
7 Correct 64 ms 156624 KB Output is correct
8 Correct 64 ms 156588 KB Output is correct
9 Correct 63 ms 156576 KB Output is correct
10 Correct 67 ms 156636 KB Output is correct
11 Correct 67 ms 156652 KB Output is correct
12 Correct 68 ms 156584 KB Output is correct
13 Correct 69 ms 156572 KB Output is correct
14 Correct 68 ms 156568 KB Output is correct
15 Correct 66 ms 156628 KB Output is correct
16 Correct 67 ms 156588 KB Output is correct
17 Correct 67 ms 156628 KB Output is correct
18 Correct 65 ms 156680 KB Output is correct
19 Correct 65 ms 156636 KB Output is correct
20 Correct 74 ms 156620 KB Output is correct
21 Correct 143 ms 156584 KB Output is correct
22 Correct 181 ms 156684 KB Output is correct
23 Correct 90 ms 156604 KB Output is correct
24 Correct 303 ms 156808 KB Output is correct
25 Correct 527 ms 156688 KB Output is correct
26 Correct 600 ms 156704 KB Output is correct
27 Correct 572 ms 156712 KB Output is correct
28 Correct 605 ms 156720 KB Output is correct
29 Correct 640 ms 156692 KB Output is correct
30 Correct 380 ms 156720 KB Output is correct
31 Correct 468 ms 156620 KB Output is correct
32 Correct 340 ms 156684 KB Output is correct
33 Correct 651 ms 156688 KB Output is correct
34 Correct 637 ms 156708 KB Output is correct
35 Correct 588 ms 156716 KB Output is correct
36 Correct 338 ms 156688 KB Output is correct
37 Execution timed out 1087 ms 156672 KB Time limit exceeded
38 Halted 0 ms 0 KB -