oj.uz

Submission #522886

# Submission time Handle Problem Language Result Execution time Memory
522886 2022-02-06T09:49:53 Z Nursik Bootfall (IZhO17_bootfall) C++14
13 / 100
 431 ms 23884 KB 
#include <bits/stdc++.h>

#define pb push_back
#define ll long long
#define ld long double
#define f first
#define s second
#define mp make_pair

const ll maxn = 1e3 + 1, maxm = 4e3 + 1,  maxk = 61;
const ll inf = 1000000000, mod = inf + 7, mod2 = 998244353;
const ll pa = 31, block = 400;

using namespace std;

ll n, x, y;
ll a[maxn], dp[maxn * maxn ], cnt[maxn * maxn], cnt2[maxn * maxn];
int main(){
  //  ios_base::sync_with_stdio(false);
   // cin.tie(0), cout.tie(0);
    cin >> n;
    dp[0] = 1;
    for (int i = 1; i <= n; ++i){
        cin >> a[i];
        for (int j = maxn * maxn; j >= 0; --j){
            if (dp[j] > 0){
                dp[j + a[i]] += dp[j];
            }
        }
        x += a[i];
    }
    if (x % 2 != 0 || dp[x / 2] == 0){
        cout << 0 << '\n';
        return 0;
    }
    for (int i = 1; i <= maxn * maxn; ++i){
        cnt[i] = 1;
    }
    for (int i = 1; i <= n; ++i){
        y = x - a[i];
        for (int j = 0; j <= maxn * maxn - a[i]; ++j){
            dp[j + a[i]] -= dp[j];
            dp[j + a[i]] = max(0ll, dp[j + a[i]]);
        }
        for (int j = 0; j <= maxn * maxn; ++j){
            if (dp[j] > 0){
                ll f = j, s = y - j;
                ll rz = abs(f - s);
                if (cnt[rz] == 1){
                    cnt2[rz] = 1;
                }
            }
        }
        for (int j = maxn * maxn - a[i]; j >= 0; --j){
            dp[j + a[i]] += dp[j];
        }
        for (int j = 1; j <= maxn * maxn; ++j){
            cnt[j] = cnt2[j];
            cnt2[j] = 0;
        }
    }
    vector<int> v;
    for (int i = 1; i <= maxn * maxn; ++i){
        if (cnt[i] > 0){
            v.pb(i);
        }
    }
    cout << v.size() << '\n';
    for (auto it : v){
        cout << it << " ";
    }
}

Compilation message

bootfall.cpp: In function 'int main()':
bootfall.cpp:37:16: warning: iteration 1002000 invokes undefined behavior [-Waggressive-loop-optimizations]
   37 |         cnt[i] = 1;
      |         ~~~~~~~^~~
bootfall.cpp:36:23: note: within this loop
   36 |     for (int i = 1; i <= maxn * maxn; ++i){
      |                     ~~^~~~~~~~~~~~~~
bootfall.cpp:46:21: warning: iteration 1002001 invokes undefined behavior [-Waggressive-loop-optimizations]
   46 |             if (dp[j] > 0){
      |                 ~~~~^
bootfall.cpp:45:27: note: within this loop
   45 |         for (int j = 0; j <= maxn * maxn; ++j){
      |                         ~~^~~~~~~~~~~~~~
bootfall.cpp:58:28: warning: iteration 1002000 invokes undefined behavior [-Waggressive-loop-optimizations]
   58 |             cnt[j] = cnt2[j];
      |                      ~~~~~~^
bootfall.cpp:57:27: note: within this loop
   57 |         for (int j = 1; j <= maxn * maxn; ++j){
      |                         ~~^~~~~~~~~~~~~~
bootfall.cpp:58:20: warning: 'void* __builtin_memcpy(void*, const void*, long unsigned int)' forming offset [8016008, 8016015] is out of the bounds [0, 8016008] of object 'cnt' with type 'long long int [1002001]' [-Warray-bounds]
   58 |             cnt[j] = cnt2[j];
      |             ~~~~~~~^~~~~~~~~
bootfall.cpp:17:31: note: 'cnt' declared here
   17 | ll a[maxn], dp[maxn * maxn ], cnt[maxn * maxn], cnt2[maxn * maxn];
      |                               ^~~
bootfall.cpp:59:21: warning: 'void* __builtin_memset(void*, int, long unsigned int)' forming offset [8016008, 8016015] is out of the bounds [0, 8016008] of object 'cnt2' with type 'long long int [1002001]' [-Warray-bounds]
   59 |             cnt2[j] = 0;
      |             ~~~~~~~~^~~
bootfall.cpp:17:49: note: 'cnt2' declared here
   17 | ll a[maxn], dp[maxn * maxn ], cnt[maxn * maxn], cnt2[maxn * maxn];
      |                                                 ^~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 23808 KB Output is correct
2 Correct 47 ms 23800 KB Output is correct
3 Correct 4 ms 204 KB Output is correct
4 Correct 36 ms 23740 KB Output is correct
5 Correct 76 ms 23884 KB Output is correct
6 Correct 57 ms 23756 KB Output is correct
7 Correct 45 ms 23800 KB Output is correct
8 Correct 75 ms 23700 KB Output is correct
9 Correct 76 ms 23804 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 23808 KB Output is correct
2 Correct 47 ms 23800 KB Output is correct
3 Correct 4 ms 204 KB Output is correct
4 Correct 36 ms 23740 KB Output is correct
5 Correct 76 ms 23884 KB Output is correct
6 Correct 57 ms 23756 KB Output is correct
7 Correct 45 ms 23800 KB Output is correct
8 Correct 75 ms 23700 KB Output is correct
9 Correct 76 ms 23804 KB Output is correct
10 Correct 199 ms 23808 KB Output is correct
11 Correct 195 ms 23804 KB Output is correct
12 Correct 191 ms 23800 KB Output is correct
13 Correct 161 ms 23736 KB Output is correct
14 Correct 168 ms 23748 KB Output is correct
15 Correct 177 ms 23804 KB Output is correct
16 Correct 204 ms 23824 KB Output is correct
17 Correct 118 ms 23800 KB Output is correct
18 Correct 147 ms 23800 KB Output is correct
19 Correct 159 ms 23764 KB Output is correct
20 Correct 187 ms 23768 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 23808 KB Output is correct
2 Correct 47 ms 23800 KB Output is correct
3 Correct 4 ms 204 KB Output is correct
4 Correct 36 ms 23740 KB Output is correct
5 Correct 76 ms 23884 KB Output is correct
6 Correct 57 ms 23756 KB Output is correct
7 Correct 45 ms 23800 KB Output is correct
8 Correct 75 ms 23700 KB Output is correct
9 Correct 76 ms 23804 KB Output is correct
10 Correct 199 ms 23808 KB Output is correct
11 Correct 195 ms 23804 KB Output is correct
12 Correct 191 ms 23800 KB Output is correct
13 Correct 161 ms 23736 KB Output is correct
14 Correct 168 ms 23748 KB Output is correct
15 Correct 177 ms 23804 KB Output is correct
16 Correct 204 ms 23824 KB Output is correct
17 Correct 118 ms 23800 KB Output is correct
18 Correct 147 ms 23800 KB Output is correct
19 Correct 159 ms 23764 KB Output is correct
20 Correct 187 ms 23768 KB Output is correct
21 Correct 347 ms 23736 KB Output is correct
22 Incorrect 431 ms 23872 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 23808 KB Output is correct
2 Correct 47 ms 23800 KB Output is correct
3 Correct 4 ms 204 KB Output is correct
4 Correct 36 ms 23740 KB Output is correct
5 Correct 76 ms 23884 KB Output is correct
6 Correct 57 ms 23756 KB Output is correct
7 Correct 45 ms 23800 KB Output is correct
8 Correct 75 ms 23700 KB Output is correct
9 Correct 76 ms 23804 KB Output is correct
10 Correct 199 ms 23808 KB Output is correct
11 Correct 195 ms 23804 KB Output is correct
12 Correct 191 ms 23800 KB Output is correct
13 Correct 161 ms 23736 KB Output is correct
14 Correct 168 ms 23748 KB Output is correct
15 Correct 177 ms 23804 KB Output is correct
16 Correct 204 ms 23824 KB Output is correct
17 Correct 118 ms 23800 KB Output is correct
18 Correct 147 ms 23800 KB Output is correct
19 Correct 159 ms 23764 KB Output is correct
20 Correct 187 ms 23768 KB Output is correct
21 Correct 347 ms 23736 KB Output is correct
22 Incorrect 431 ms 23872 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 23808 KB Output is correct
2 Correct 47 ms 23800 KB Output is correct
3 Correct 4 ms 204 KB Output is correct
4 Correct 36 ms 23740 KB Output is correct
5 Correct 76 ms 23884 KB Output is correct
6 Correct 57 ms 23756 KB Output is correct
7 Correct 45 ms 23800 KB Output is correct
8 Correct 75 ms 23700 KB Output is correct
9 Correct 76 ms 23804 KB Output is correct
10 Correct 199 ms 23808 KB Output is correct
11 Correct 195 ms 23804 KB Output is correct
12 Correct 191 ms 23800 KB Output is correct
13 Correct 161 ms 23736 KB Output is correct
14 Correct 168 ms 23748 KB Output is correct
15 Correct 177 ms 23804 KB Output is correct
16 Correct 204 ms 23824 KB Output is correct
17 Correct 118 ms 23800 KB Output is correct
18 Correct 147 ms 23800 KB Output is correct
19 Correct 159 ms 23764 KB Output is correct
20 Correct 187 ms 23768 KB Output is correct
21 Correct 347 ms 23736 KB Output is correct
22 Incorrect 431 ms 23872 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 23808 KB Output is correct
2 Correct 47 ms 23800 KB Output is correct
3 Correct 4 ms 204 KB Output is correct
4 Correct 36 ms 23740 KB Output is correct
5 Correct 76 ms 23884 KB Output is correct
6 Correct 57 ms 23756 KB Output is correct
7 Correct 45 ms 23800 KB Output is correct
8 Correct 75 ms 23700 KB Output is correct
9 Correct 76 ms 23804 KB Output is correct
10 Correct 199 ms 23808 KB Output is correct
11 Correct 195 ms 23804 KB Output is correct
12 Correct 191 ms 23800 KB Output is correct
13 Correct 161 ms 23736 KB Output is correct
14 Correct 168 ms 23748 KB Output is correct
15 Correct 177 ms 23804 KB Output is correct
16 Correct 204 ms 23824 KB Output is correct
17 Correct 118 ms 23800 KB Output is correct
18 Correct 147 ms 23800 KB Output is correct
19 Correct 159 ms 23764 KB Output is correct
20 Correct 187 ms 23768 KB Output is correct
21 Correct 347 ms 23736 KB Output is correct
22 Incorrect 431 ms 23872 KB Output isn't correct
23 Halted 0 ms 0 KB -