oj.uz

Submission #492924

# Submission time Handle Problem Language Result Execution time Memory
492924 2021-12-09T18:37:26 Z White Bootfall (IZhO17_bootfall) C++14
13 / 100
 1000 ms 32296 KB 
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

int n,red[501],bqh[501][250001],s;
vector<int>ans;

void dp(int v,int wrong,int to,int sbor){
    //cout<<endl<<v<<" "<<wrong<<" "<<to<<" "<<sbor<<endl;
    if(sbor>s || v>n || bqh[v][sbor]==to)return ;
    bqh[v][sbor]=to;
    if(v==wrong)dp(v+1,wrong,to,sbor);
    else{
        dp(v+1,wrong,to,sbor);
        dp(v+1,wrong,to,sbor+red[v]);
    }
    return ;
}

int main (){

    //ios_base::sync_with_stdio(false);
    //cin.tie(NULL);

    int sum=0;
    bool krai;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>red[i];
        sum+=red[i];
    }

    for(red[0]=1;red[0]<=sum-red[0];red[0]++){
        sum++;
        krai=false;
        for(int i=0;i<=n && krai==false;i++){
            s=sum-red[i];
            //cout<<s<<i<<endl;
            if(s%2==1 || s<=0)krai=true;
            else{
                dp(0,i,i+1,0);
                if(bqh[n][s/2]!=i+1)krai=true;
            }
        }
        if(krai==false)ans.push_back(red[0]);
        for(int i=0;i<=125001;i++){
            for(int j=0;j<=n;j++){
                bqh[j][i]=0;
            }
        }
    }

    cout<<ans.size()<<endl;
    for(int i=0;i<ans.size();i++)cout<<ans[i]<<" ";
    cout<<endl;

    return 0;
}

Compilation message

bootfall.cpp: In function 'int main()':
bootfall.cpp:56:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for(int i=0;i<ans.size();i++)cout<<ans[i]<<" ";
      |                 ~^~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2764 KB Output is correct
2 Correct 8 ms 3764 KB Output is correct
3 Correct 2 ms 2252 KB Output is correct
4 Correct 75 ms 2764 KB Output is correct
5 Correct 387 ms 6724 KB Output is correct
6 Correct 36 ms 4684 KB Output is correct
7 Correct 45 ms 3756 KB Output is correct
8 Correct 615 ms 6704 KB Output is correct
9 Correct 154 ms 5716 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2764 KB Output is correct
2 Correct 8 ms 3764 KB Output is correct
3 Correct 2 ms 2252 KB Output is correct
4 Correct 75 ms 2764 KB Output is correct
5 Correct 387 ms 6724 KB Output is correct
6 Correct 36 ms 4684 KB Output is correct
7 Correct 45 ms 3756 KB Output is correct
8 Correct 615 ms 6704 KB Output is correct
9 Correct 154 ms 5716 KB Output is correct
10 Correct 902 ms 15600 KB Output is correct
11 Correct 596 ms 15600 KB Output is correct
12 Correct 640 ms 15596 KB Output is correct
13 Correct 355 ms 13620 KB Output is correct
14 Correct 656 ms 14604 KB Output is correct
15 Correct 436 ms 14616 KB Output is correct
16 Correct 571 ms 15592 KB Output is correct
17 Correct 205 ms 9796 KB Output is correct
18 Correct 421 ms 12628 KB Output is correct
19 Correct 360 ms 13624 KB Output is correct
20 Correct 961 ms 15596 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2764 KB Output is correct
2 Correct 8 ms 3764 KB Output is correct
3 Correct 2 ms 2252 KB Output is correct
4 Correct 75 ms 2764 KB Output is correct
5 Correct 387 ms 6724 KB Output is correct
6 Correct 36 ms 4684 KB Output is correct
7 Correct 45 ms 3756 KB Output is correct
8 Correct 615 ms 6704 KB Output is correct
9 Correct 154 ms 5716 KB Output is correct
10 Correct 902 ms 15600 KB Output is correct
11 Correct 596 ms 15600 KB Output is correct
12 Correct 640 ms 15596 KB Output is correct
13 Correct 355 ms 13620 KB Output is correct
14 Correct 656 ms 14604 KB Output is correct
15 Correct 436 ms 14616 KB Output is correct
16 Correct 571 ms 15592 KB Output is correct
17 Correct 205 ms 9796 KB Output is correct
18 Correct 421 ms 12628 KB Output is correct
19 Correct 360 ms 13624 KB Output is correct
20 Correct 961 ms 15596 KB Output is correct
21 Execution timed out 1095 ms 32296 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2764 KB Output is correct
2 Correct 8 ms 3764 KB Output is correct
3 Correct 2 ms 2252 KB Output is correct
4 Correct 75 ms 2764 KB Output is correct
5 Correct 387 ms 6724 KB Output is correct
6 Correct 36 ms 4684 KB Output is correct
7 Correct 45 ms 3756 KB Output is correct
8 Correct 615 ms 6704 KB Output is correct
9 Correct 154 ms 5716 KB Output is correct
10 Correct 902 ms 15600 KB Output is correct
11 Correct 596 ms 15600 KB Output is correct
12 Correct 640 ms 15596 KB Output is correct
13 Correct 355 ms 13620 KB Output is correct
14 Correct 656 ms 14604 KB Output is correct
15 Correct 436 ms 14616 KB Output is correct
16 Correct 571 ms 15592 KB Output is correct
17 Correct 205 ms 9796 KB Output is correct
18 Correct 421 ms 12628 KB Output is correct
19 Correct 360 ms 13624 KB Output is correct
20 Correct 961 ms 15596 KB Output is correct
21 Execution timed out 1095 ms 32296 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2764 KB Output is correct
2 Correct 8 ms 3764 KB Output is correct
3 Correct 2 ms 2252 KB Output is correct
4 Correct 75 ms 2764 KB Output is correct
5 Correct 387 ms 6724 KB Output is correct
6 Correct 36 ms 4684 KB Output is correct
7 Correct 45 ms 3756 KB Output is correct
8 Correct 615 ms 6704 KB Output is correct
9 Correct 154 ms 5716 KB Output is correct
10 Correct 902 ms 15600 KB Output is correct
11 Correct 596 ms 15600 KB Output is correct
12 Correct 640 ms 15596 KB Output is correct
13 Correct 355 ms 13620 KB Output is correct
14 Correct 656 ms 14604 KB Output is correct
15 Correct 436 ms 14616 KB Output is correct
16 Correct 571 ms 15592 KB Output is correct
17 Correct 205 ms 9796 KB Output is correct
18 Correct 421 ms 12628 KB Output is correct
19 Correct 360 ms 13624 KB Output is correct
20 Correct 961 ms 15596 KB Output is correct
21 Execution timed out 1095 ms 32296 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2764 KB Output is correct
2 Correct 8 ms 3764 KB Output is correct
3 Correct 2 ms 2252 KB Output is correct
4 Correct 75 ms 2764 KB Output is correct
5 Correct 387 ms 6724 KB Output is correct
6 Correct 36 ms 4684 KB Output is correct
7 Correct 45 ms 3756 KB Output is correct
8 Correct 615 ms 6704 KB Output is correct
9 Correct 154 ms 5716 KB Output is correct
10 Correct 902 ms 15600 KB Output is correct
11 Correct 596 ms 15600 KB Output is correct
12 Correct 640 ms 15596 KB Output is correct
13 Correct 355 ms 13620 KB Output is correct
14 Correct 656 ms 14604 KB Output is correct
15 Correct 436 ms 14616 KB Output is correct
16 Correct 571 ms 15592 KB Output is correct
17 Correct 205 ms 9796 KB Output is correct
18 Correct 421 ms 12628 KB Output is correct
19 Correct 360 ms 13624 KB Output is correct
20 Correct 961 ms 15596 KB Output is correct
21 Execution timed out 1095 ms 32296 KB Time limit exceeded
22 Halted 0 ms 0 KB -