oj.uz

답안 #1029932

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1029932 2024-07-21T14:05:10 Z andrewp Bootfall (IZhO17_bootfall) C++14
13 / 100
 50 ms 6232 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll int64_t
#define ar array
#define dbg(x) cerr << #x << ": " << x << "\n";

const int mxN=503;

ll n, a[mxN], dp[mxN*mxN][2], brM[mxN*mxN];

int main() {
    ios::sync_with_stdio(0);
	cin.tie(0);

    cin >> n;
    ll sum=0;
    for(ll i=1; i<=n; ++i) {
        cin >> a[i];
        sum+=a[i];
    }
    dp[0][0]=1;
    for(ll i=1; i<=n; ++i) {
        for(ll s=mxN*mxN-1; s>=a[i]; --s) {
            dp[s][0]+=dp[s-a[i]][0];
        }
    }
    if(sum%2==1) {
        cout << 0 << "\n";
        return 0;
    }
    if(dp[sum/2][0]==0) {
        cout << 0 << "\n";
        return 0;
    }
    for(ll i=1; i<=n; ++i) {
        for(ll s=0; s<mxN*mxN; ++s) {
            dp[s][1]=dp[s][0];
        }
        for(ll s=0; s<mxN*mxN-a[i]; ++s) {
            dp[s+a[i]][1]-=dp[s][1];
        }
        for(ll s=0; s<mxN*mxN; ++s) {
            ll get=s+sum-a[i];
            if((get%2==0)&&(get/2>=s)&&(dp[get/2-s][1]>0)) {
                ++brM[s];
            }
        }
    }
    vector<ll> ans;
    for(ll s=0; s<mxN*mxN; ++s) {
        if(brM[s]==n) ans.push_back(s);
    }
    cout << ans.size() << "\n";
    for(ll x:ans) cout << x << " ";
    cout << "\n";
    return 0;
}

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5976 KB Output is correct
2 Correct 9 ms 6108 KB Output is correct
3 Correct 4 ms 5976 KB Output is correct
4 Correct 7 ms 5980 KB Output is correct
5 Correct 9 ms 6232 KB Output is correct
6 Correct 10 ms 5980 KB Output is correct
7 Correct 6 ms 5980 KB Output is correct
8 Correct 11 ms 4384 KB Output is correct
9 Correct 12 ms 4188 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5976 KB Output is correct
2 Correct 9 ms 6108 KB Output is correct
3 Correct 4 ms 5976 KB Output is correct
4 Correct 7 ms 5980 KB Output is correct
5 Correct 9 ms 6232 KB Output is correct
6 Correct 10 ms 5980 KB Output is correct
7 Correct 6 ms 5980 KB Output is correct
8 Correct 11 ms 4384 KB Output is correct
9 Correct 12 ms 4188 KB Output is correct
10 Correct 21 ms 4184 KB Output is correct
11 Correct 20 ms 4416 KB Output is correct
12 Correct 21 ms 4188 KB Output is correct
13 Correct 24 ms 4432 KB Output is correct
14 Correct 20 ms 4188 KB Output is correct
15 Correct 28 ms 4188 KB Output is correct
16 Correct 27 ms 4188 KB Output is correct
17 Correct 14 ms 4184 KB Output is correct
18 Correct 21 ms 4184 KB Output is correct
19 Correct 26 ms 4408 KB Output is correct
20 Correct 27 ms 4188 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5976 KB Output is correct
2 Correct 9 ms 6108 KB Output is correct
3 Correct 4 ms 5976 KB Output is correct
4 Correct 7 ms 5980 KB Output is correct
5 Correct 9 ms 6232 KB Output is correct
6 Correct 10 ms 5980 KB Output is correct
7 Correct 6 ms 5980 KB Output is correct
8 Correct 11 ms 4384 KB Output is correct
9 Correct 12 ms 4188 KB Output is correct
10 Correct 21 ms 4184 KB Output is correct
11 Correct 20 ms 4416 KB Output is correct
12 Correct 21 ms 4188 KB Output is correct
13 Correct 24 ms 4432 KB Output is correct
14 Correct 20 ms 4188 KB Output is correct
15 Correct 28 ms 4188 KB Output is correct
16 Correct 27 ms 4188 KB Output is correct
17 Correct 14 ms 4184 KB Output is correct
18 Correct 21 ms 4184 KB Output is correct
19 Correct 26 ms 4408 KB Output is correct
20 Correct 27 ms 4188 KB Output is correct
21 Correct 50 ms 4432 KB Output is correct
22 Incorrect 44 ms 4444 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5976 KB Output is correct
2 Correct 9 ms 6108 KB Output is correct
3 Correct 4 ms 5976 KB Output is correct
4 Correct 7 ms 5980 KB Output is correct
5 Correct 9 ms 6232 KB Output is correct
6 Correct 10 ms 5980 KB Output is correct
7 Correct 6 ms 5980 KB Output is correct
8 Correct 11 ms 4384 KB Output is correct
9 Correct 12 ms 4188 KB Output is correct
10 Correct 21 ms 4184 KB Output is correct
11 Correct 20 ms 4416 KB Output is correct
12 Correct 21 ms 4188 KB Output is correct
13 Correct 24 ms 4432 KB Output is correct
14 Correct 20 ms 4188 KB Output is correct
15 Correct 28 ms 4188 KB Output is correct
16 Correct 27 ms 4188 KB Output is correct
17 Correct 14 ms 4184 KB Output is correct
18 Correct 21 ms 4184 KB Output is correct
19 Correct 26 ms 4408 KB Output is correct
20 Correct 27 ms 4188 KB Output is correct
21 Correct 50 ms 4432 KB Output is correct
22 Incorrect 44 ms 4444 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5976 KB Output is correct
2 Correct 9 ms 6108 KB Output is correct
3 Correct 4 ms 5976 KB Output is correct
4 Correct 7 ms 5980 KB Output is correct
5 Correct 9 ms 6232 KB Output is correct
6 Correct 10 ms 5980 KB Output is correct
7 Correct 6 ms 5980 KB Output is correct
8 Correct 11 ms 4384 KB Output is correct
9 Correct 12 ms 4188 KB Output is correct
10 Correct 21 ms 4184 KB Output is correct
11 Correct 20 ms 4416 KB Output is correct
12 Correct 21 ms 4188 KB Output is correct
13 Correct 24 ms 4432 KB Output is correct
14 Correct 20 ms 4188 KB Output is correct
15 Correct 28 ms 4188 KB Output is correct
16 Correct 27 ms 4188 KB Output is correct
17 Correct 14 ms 4184 KB Output is correct
18 Correct 21 ms 4184 KB Output is correct
19 Correct 26 ms 4408 KB Output is correct
20 Correct 27 ms 4188 KB Output is correct
21 Correct 50 ms 4432 KB Output is correct
22 Incorrect 44 ms 4444 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5976 KB Output is correct
2 Correct 9 ms 6108 KB Output is correct
3 Correct 4 ms 5976 KB Output is correct
4 Correct 7 ms 5980 KB Output is correct
5 Correct 9 ms 6232 KB Output is correct
6 Correct 10 ms 5980 KB Output is correct
7 Correct 6 ms 5980 KB Output is correct
8 Correct 11 ms 4384 KB Output is correct
9 Correct 12 ms 4188 KB Output is correct
10 Correct 21 ms 4184 KB Output is correct
11 Correct 20 ms 4416 KB Output is correct
12 Correct 21 ms 4188 KB Output is correct
13 Correct 24 ms 4432 KB Output is correct
14 Correct 20 ms 4188 KB Output is correct
15 Correct 28 ms 4188 KB Output is correct
16 Correct 27 ms 4188 KB Output is correct
17 Correct 14 ms 4184 KB Output is correct
18 Correct 21 ms 4184 KB Output is correct
19 Correct 26 ms 4408 KB Output is correct
20 Correct 27 ms 4188 KB Output is correct
21 Correct 50 ms 4432 KB Output is correct
22 Incorrect 44 ms 4444 KB Output isn't correct
23 Halted 0 ms 0 KB -