oj.uz

Submission #566237

# Submission time Handle Problem Language Result Execution time Memory
566237 2022-05-22T07:37:18 Z shrimb Bootfall (IZhO17_bootfall) C++17
13 / 100
 1000 ms 156156 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;

int dp[maxn][maxn*maxn];
bitset<maxn*maxn> ans;
int n, tot, ex, total;
int a[maxn];

int rec (int i, int sm) {
    if (sm < 0) return 0;
    if (i == n) return sm == 0;
    if (i == ex) return rec(i + 1, sm);
    if (dp[i][sm] != -1) return dp[i][sm];
    return dp[i][sm] = rec(i + 1, sm) | rec(i + 1, sm - a[i]);
}

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;
    memset(dp, -1,sizeof dp);
    if (!rec(0, total / 2)) {
        cout << 0 << endl;
        return 0;
    }
    ans[0] = 0;
    for (int i = 0 ; i < n ; i++) {
        tot = total - a[i];
        ex = i;
        memset(dp, -1,sizeof dp);
        for (int j = 1 ; j <= total ; j++) {
            if ((tot+j)&1||!rec(0, (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 119 ms 155980 KB Output is correct
2 Correct 151 ms 156156 KB Output is correct
3 Correct 63 ms 156020 KB Output is correct
4 Correct 124 ms 156092 KB Output is correct
5 Correct 248 ms 156092 KB Output is correct
6 Correct 187 ms 156112 KB Output is correct
7 Correct 162 ms 155968 KB Output is correct
8 Correct 243 ms 156068 KB Output is correct
9 Correct 215 ms 156088 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 155980 KB Output is correct
2 Correct 151 ms 156156 KB Output is correct
3 Correct 63 ms 156020 KB Output is correct
4 Correct 124 ms 156092 KB Output is correct
5 Correct 248 ms 156092 KB Output is correct
6 Correct 187 ms 156112 KB Output is correct
7 Correct 162 ms 155968 KB Output is correct
8 Correct 243 ms 156068 KB Output is correct
9 Correct 215 ms 156088 KB Output is correct
10 Correct 530 ms 156088 KB Output is correct
11 Correct 539 ms 156096 KB Output is correct
12 Correct 536 ms 156096 KB Output is correct
13 Correct 460 ms 156092 KB Output is correct
14 Correct 496 ms 156100 KB Output is correct
15 Correct 506 ms 155992 KB Output is correct
16 Correct 537 ms 156096 KB Output is correct
17 Correct 341 ms 156104 KB Output is correct
18 Correct 433 ms 156092 KB Output is correct
19 Correct 469 ms 156124 KB Output is correct
20 Correct 549 ms 156092 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 155980 KB Output is correct
2 Correct 151 ms 156156 KB Output is correct
3 Correct 63 ms 156020 KB Output is correct
4 Correct 124 ms 156092 KB Output is correct
5 Correct 248 ms 156092 KB Output is correct
6 Correct 187 ms 156112 KB Output is correct
7 Correct 162 ms 155968 KB Output is correct
8 Correct 243 ms 156068 KB Output is correct
9 Correct 215 ms 156088 KB Output is correct
10 Correct 530 ms 156088 KB Output is correct
11 Correct 539 ms 156096 KB Output is correct
12 Correct 536 ms 156096 KB Output is correct
13 Correct 460 ms 156092 KB Output is correct
14 Correct 496 ms 156100 KB Output is correct
15 Correct 506 ms 155992 KB Output is correct
16 Correct 537 ms 156096 KB Output is correct
17 Correct 341 ms 156104 KB Output is correct
18 Correct 433 ms 156092 KB Output is correct
19 Correct 469 ms 156124 KB Output is correct
20 Correct 549 ms 156092 KB Output is correct
21 Execution timed out 1082 ms 156048 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 155980 KB Output is correct
2 Correct 151 ms 156156 KB Output is correct
3 Correct 63 ms 156020 KB Output is correct
4 Correct 124 ms 156092 KB Output is correct
5 Correct 248 ms 156092 KB Output is correct
6 Correct 187 ms 156112 KB Output is correct
7 Correct 162 ms 155968 KB Output is correct
8 Correct 243 ms 156068 KB Output is correct
9 Correct 215 ms 156088 KB Output is correct
10 Correct 530 ms 156088 KB Output is correct
11 Correct 539 ms 156096 KB Output is correct
12 Correct 536 ms 156096 KB Output is correct
13 Correct 460 ms 156092 KB Output is correct
14 Correct 496 ms 156100 KB Output is correct
15 Correct 506 ms 155992 KB Output is correct
16 Correct 537 ms 156096 KB Output is correct
17 Correct 341 ms 156104 KB Output is correct
18 Correct 433 ms 156092 KB Output is correct
19 Correct 469 ms 156124 KB Output is correct
20 Correct 549 ms 156092 KB Output is correct
21 Execution timed out 1082 ms 156048 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 155980 KB Output is correct
2 Correct 151 ms 156156 KB Output is correct
3 Correct 63 ms 156020 KB Output is correct
4 Correct 124 ms 156092 KB Output is correct
5 Correct 248 ms 156092 KB Output is correct
6 Correct 187 ms 156112 KB Output is correct
7 Correct 162 ms 155968 KB Output is correct
8 Correct 243 ms 156068 KB Output is correct
9 Correct 215 ms 156088 KB Output is correct
10 Correct 530 ms 156088 KB Output is correct
11 Correct 539 ms 156096 KB Output is correct
12 Correct 536 ms 156096 KB Output is correct
13 Correct 460 ms 156092 KB Output is correct
14 Correct 496 ms 156100 KB Output is correct
15 Correct 506 ms 155992 KB Output is correct
16 Correct 537 ms 156096 KB Output is correct
17 Correct 341 ms 156104 KB Output is correct
18 Correct 433 ms 156092 KB Output is correct
19 Correct 469 ms 156124 KB Output is correct
20 Correct 549 ms 156092 KB Output is correct
21 Execution timed out 1082 ms 156048 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 155980 KB Output is correct
2 Correct 151 ms 156156 KB Output is correct
3 Correct 63 ms 156020 KB Output is correct
4 Correct 124 ms 156092 KB Output is correct
5 Correct 248 ms 156092 KB Output is correct
6 Correct 187 ms 156112 KB Output is correct
7 Correct 162 ms 155968 KB Output is correct
8 Correct 243 ms 156068 KB Output is correct
9 Correct 215 ms 156088 KB Output is correct
10 Correct 530 ms 156088 KB Output is correct
11 Correct 539 ms 156096 KB Output is correct
12 Correct 536 ms 156096 KB Output is correct
13 Correct 460 ms 156092 KB Output is correct
14 Correct 496 ms 156100 KB Output is correct
15 Correct 506 ms 155992 KB Output is correct
16 Correct 537 ms 156096 KB Output is correct
17 Correct 341 ms 156104 KB Output is correct
18 Correct 433 ms 156092 KB Output is correct
19 Correct 469 ms 156124 KB Output is correct
20 Correct 549 ms 156092 KB Output is correct
21 Execution timed out 1082 ms 156048 KB Time limit exceeded
22 Halted 0 ms 0 KB -