답안 #167619

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
167619	2019-12-09T06:16:40 Z	Rakhmand	Bootfall (IZhO17_bootfall)	C++14	13 / 100	137 ms	21228 KB

bootfall

//
//  ROIGold.cpp
//  Main calisma
//
//  Created by Rakhman on 05/02/2019.
//  Copyright © 2019 Rakhman. All rights reserved.
//
 
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <iterator>
 
#define ios ios_base::sync_with_stdio(0), cout.tie(0), cin.tie(0);
#define S second
#define F first
#define pb push_back
#define nl '\n'
#define NL cout << '\n';
#define EX exit(0)
#define all(s) s.begin(), s.end()
#define no_answer return cout << 0, 0;
#define FOR(i, start, finish, k) for(int i = start; i <= finish; i += k)
 
const int MXN = 4e5 + 200;
const long long MNN = 4e2 + 200;
const long long MOD = 1e9 + 7;
const long long INF = 1e18;
const int OO = 1e9 + 500;
 
typedef long long llong;
typedef unsigned long long ullong;
 
using namespace std;
 
int n, k, a[MXN], cnt, pos[2000000], num[100000000], dp[510][510][510];
int sum = 0;
vector<int> v;

void precalc(){
    bitset<126000> p;
    p[0] = 1;
    for(int i = 1; i <= n; i++){
        p |= p << a[i];
    }
    if(p[sum / 2] == 0) {
        cout << 0;
        exit(0);
    }
    int kek = 0;
    for(int i = 0; i <= sum; i++){
        if(p[i] == 1){
            pos[i] = kek;
            num[kek] = i;
            kek++;
        }
        else{
            pos[i] = -1;
        }
    }
    dp[0][1][0] = 1;
    for(int no = 1; no <= n; no++){
        dp[no][0][0] = 1;
        for(int i = 1; i <= n; i++){
            for(int j = 0; j <= pos[sum]; j++){
                dp[no][i][j] = dp[no][i - 1][j];
                int l = num[j];
                if(num[j] - a[i] >= 0 && pos[l - a[i]] != -1 && i != no){
                    dp[no][i][j] |= dp[no][i - 1][pos[l - a[i]]];
                }
            }
        }
    }
}






int main () {
    ios;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        sum += a[i];
        cnt += a[i] % 2;
    }
    if(sum % 2 == 1) no_answer;
    if(cnt != 0 && cnt != n) no_answer;
    precalc();
    for(int i = a[1] % 2; i <= sum; i += 2){
        bool ok = 1;
        for(int j = 1; j <= n; j++){
            if((sum + i - a[j]) / 2 - i < 0 || pos[(sum + i - a[j]) / 2 - i] == -1 || dp[j][n][pos[(sum + i - a[j]) / 2 - i]] == 0){
                ok = 0;
                break;
            }
        }
        if(ok == 1) v.pb(i);
    }
    cout << v.size() << nl;
    for(int i = 0; i < v.size(); i++){
        cout << v[i] << ' ';
    }
}

Compilation message

bootfall.cpp: In function 'int main()':
bootfall.cpp:121:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v.size(); i++){
                    ~~^~~~~~~~~~

Subtask #1
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	2 ms	632 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	504 KB	Output is correct
5	Correct	3 ms	760 KB	Output is correct
6	Correct	2 ms	504 KB	Output is correct
7	Correct	2 ms	508 KB	Output is correct
8	Correct	2 ms	888 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	2 ms	632 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	504 KB	Output is correct
5	Correct	3 ms	760 KB	Output is correct
6	Correct	2 ms	504 KB	Output is correct
7	Correct	2 ms	508 KB	Output is correct
8	Correct	2 ms	888 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	4 ms	2424 KB	Output is correct
11	Correct	4 ms	2552 KB	Output is correct
12	Correct	4 ms	2424 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	5 ms	2296 KB	Output is correct
15	Correct	4 ms	2168 KB	Output is correct
16	Correct	4 ms	2424 KB	Output is correct
17	Correct	3 ms	1144 KB	Output is correct
18	Correct	4 ms	1784 KB	Output is correct
19	Correct	4 ms	1912 KB	Output is correct
20	Correct	6 ms	2424 KB	Output is correct

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	2 ms	632 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	504 KB	Output is correct
5	Correct	3 ms	760 KB	Output is correct
6	Correct	2 ms	504 KB	Output is correct
7	Correct	2 ms	508 KB	Output is correct
8	Correct	2 ms	888 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	4 ms	2424 KB	Output is correct
11	Correct	4 ms	2552 KB	Output is correct
12	Correct	4 ms	2424 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	5 ms	2296 KB	Output is correct
15	Correct	4 ms	2168 KB	Output is correct
16	Correct	4 ms	2424 KB	Output is correct
17	Correct	3 ms	1144 KB	Output is correct
18	Correct	4 ms	1784 KB	Output is correct
19	Correct	4 ms	1912 KB	Output is correct
20	Correct	6 ms	2424 KB	Output is correct
21	Correct	34 ms	9676 KB	Output is correct
22	Correct	47 ms	12900 KB	Output is correct
23	Correct	19 ms	6264 KB	Output is correct
24	Correct	93 ms	20440 KB	Output is correct
25	Incorrect	137 ms	21228 KB	Output isn't correct
26	Halted	0 ms	0 KB	-

Subtask #4
0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	2 ms	632 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	504 KB	Output is correct
5	Correct	3 ms	760 KB	Output is correct
6	Correct	2 ms	504 KB	Output is correct
7	Correct	2 ms	508 KB	Output is correct
8	Correct	2 ms	888 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	4 ms	2424 KB	Output is correct
11	Correct	4 ms	2552 KB	Output is correct
12	Correct	4 ms	2424 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	5 ms	2296 KB	Output is correct
15	Correct	4 ms	2168 KB	Output is correct
16	Correct	4 ms	2424 KB	Output is correct
17	Correct	3 ms	1144 KB	Output is correct
18	Correct	4 ms	1784 KB	Output is correct
19	Correct	4 ms	1912 KB	Output is correct
20	Correct	6 ms	2424 KB	Output is correct
21	Correct	34 ms	9676 KB	Output is correct
22	Correct	47 ms	12900 KB	Output is correct
23	Correct	19 ms	6264 KB	Output is correct
24	Correct	93 ms	20440 KB	Output is correct
25	Incorrect	137 ms	21228 KB	Output isn't correct
26	Halted	0 ms	0 KB	-

Subtask #5
0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	2 ms	632 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	504 KB	Output is correct
5	Correct	3 ms	760 KB	Output is correct
6	Correct	2 ms	504 KB	Output is correct
7	Correct	2 ms	508 KB	Output is correct
8	Correct	2 ms	888 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	4 ms	2424 KB	Output is correct
11	Correct	4 ms	2552 KB	Output is correct
12	Correct	4 ms	2424 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	5 ms	2296 KB	Output is correct
15	Correct	4 ms	2168 KB	Output is correct
16	Correct	4 ms	2424 KB	Output is correct
17	Correct	3 ms	1144 KB	Output is correct
18	Correct	4 ms	1784 KB	Output is correct
19	Correct	4 ms	1912 KB	Output is correct
20	Correct	6 ms	2424 KB	Output is correct
21	Correct	34 ms	9676 KB	Output is correct
22	Correct	47 ms	12900 KB	Output is correct
23	Correct	19 ms	6264 KB	Output is correct
24	Correct	93 ms	20440 KB	Output is correct
25	Incorrect	137 ms	21228 KB	Output isn't correct
26	Halted	0 ms	0 KB	-

Subtask #6
0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	2 ms	632 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	504 KB	Output is correct
5	Correct	3 ms	760 KB	Output is correct
6	Correct	2 ms	504 KB	Output is correct
7	Correct	2 ms	508 KB	Output is correct
8	Correct	2 ms	888 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	4 ms	2424 KB	Output is correct
11	Correct	4 ms	2552 KB	Output is correct
12	Correct	4 ms	2424 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	5 ms	2296 KB	Output is correct
15	Correct	4 ms	2168 KB	Output is correct
16	Correct	4 ms	2424 KB	Output is correct
17	Correct	3 ms	1144 KB	Output is correct
18	Correct	4 ms	1784 KB	Output is correct
19	Correct	4 ms	1912 KB	Output is correct
20	Correct	6 ms	2424 KB	Output is correct
21	Correct	34 ms	9676 KB	Output is correct
22	Correct	47 ms	12900 KB	Output is correct
23	Correct	19 ms	6264 KB	Output is correct
24	Correct	93 ms	20440 KB	Output is correct
25	Incorrect	137 ms	21228 KB	Output isn't correct
26	Halted	0 ms	0 KB	-

답안 #167619

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 7.0 / 7.0

Subtask #3 0 / 15.0

Subtask #4 0 / 16.0

Subtask #5 0 / 21.0

Subtask #6 0 / 35.0

Subtask #1
6.0 / 6.0

Subtask #2
7.0 / 7.0

Subtask #3
0 / 15.0

Subtask #4
0 / 16.0

Subtask #5
0 / 21.0

Subtask #6
0 / 35.0