답안 #167620

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
167620	2019-12-09T06:21:59 Z	Rakhmand	Bootfall (IZhO17_bootfall)	C++14	13 / 100	135 ms	21240 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[1000000], 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){
                ok = 0;
                break;
            }
            if(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:125: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	504 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	504 KB	Output is correct
8	Correct	3 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	504 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	504 KB	Output is correct
8	Correct	3 ms	888 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	4 ms	2428 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	4 ms	2296 KB	Output is correct
15	Correct	4 ms	2300 KB	Output is correct
16	Correct	4 ms	2552 KB	Output is correct
17	Correct	3 ms	1192 KB	Output is correct
18	Correct	3 ms	1784 KB	Output is correct
19	Correct	4 ms	1912 KB	Output is correct
20	Correct	4 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	504 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	504 KB	Output is correct
8	Correct	3 ms	888 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	4 ms	2428 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	4 ms	2296 KB	Output is correct
15	Correct	4 ms	2300 KB	Output is correct
16	Correct	4 ms	2552 KB	Output is correct
17	Correct	3 ms	1192 KB	Output is correct
18	Correct	3 ms	1784 KB	Output is correct
19	Correct	4 ms	1912 KB	Output is correct
20	Correct	4 ms	2424 KB	Output is correct
21	Correct	33 ms	9720 KB	Output is correct
22	Correct	47 ms	12920 KB	Output is correct
23	Correct	18 ms	6392 KB	Output is correct
24	Correct	93 ms	20368 KB	Output is correct
25	Incorrect	135 ms	21240 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	504 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	504 KB	Output is correct
8	Correct	3 ms	888 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	4 ms	2428 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	4 ms	2296 KB	Output is correct
15	Correct	4 ms	2300 KB	Output is correct
16	Correct	4 ms	2552 KB	Output is correct
17	Correct	3 ms	1192 KB	Output is correct
18	Correct	3 ms	1784 KB	Output is correct
19	Correct	4 ms	1912 KB	Output is correct
20	Correct	4 ms	2424 KB	Output is correct
21	Correct	33 ms	9720 KB	Output is correct
22	Correct	47 ms	12920 KB	Output is correct
23	Correct	18 ms	6392 KB	Output is correct
24	Correct	93 ms	20368 KB	Output is correct
25	Incorrect	135 ms	21240 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	504 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	504 KB	Output is correct
8	Correct	3 ms	888 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	4 ms	2428 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	4 ms	2296 KB	Output is correct
15	Correct	4 ms	2300 KB	Output is correct
16	Correct	4 ms	2552 KB	Output is correct
17	Correct	3 ms	1192 KB	Output is correct
18	Correct	3 ms	1784 KB	Output is correct
19	Correct	4 ms	1912 KB	Output is correct
20	Correct	4 ms	2424 KB	Output is correct
21	Correct	33 ms	9720 KB	Output is correct
22	Correct	47 ms	12920 KB	Output is correct
23	Correct	18 ms	6392 KB	Output is correct
24	Correct	93 ms	20368 KB	Output is correct
25	Incorrect	135 ms	21240 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	504 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	504 KB	Output is correct
8	Correct	3 ms	888 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	4 ms	2428 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	4 ms	2296 KB	Output is correct
15	Correct	4 ms	2300 KB	Output is correct
16	Correct	4 ms	2552 KB	Output is correct
17	Correct	3 ms	1192 KB	Output is correct
18	Correct	3 ms	1784 KB	Output is correct
19	Correct	4 ms	1912 KB	Output is correct
20	Correct	4 ms	2424 KB	Output is correct
21	Correct	33 ms	9720 KB	Output is correct
22	Correct	47 ms	12920 KB	Output is correct
23	Correct	18 ms	6392 KB	Output is correct
24	Correct	93 ms	20368 KB	Output is correct
25	Incorrect	135 ms	21240 KB	Output isn't correct
26	Halted	0 ms	0 KB	-

답안 #167620

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