oj.uz

Submission #834161

# Submission time Handle Problem Language Result Execution time Memory
834161 2023-08-22T11:23:40 Z Knight Kpart (eJOI21_kpart) C++14
10 / 100
 2000 ms 460 KB 
#include <iostream>
using namespace std;


int main(){
    int T, N, count, sum, halfSum;
    bool test;
    bool testL[50001];
    testL[0] = true;
    for(int i=1;i<=50000;i++) testL[i] = false;
    int tempL[1000];
    int Klist[999];
    int A[1000];
    cin >> T;

    for(int t=0;t<T;t++){ // input
        cin >> N;
        for(int i=0;i<N;i++){
            cin >> A[i];
        }
        count = 0;

        for(int k=2;k<=N;k++){ // start of actual code
            test = true;

            for(int i=0;i<=N-k;i++){ // choose sub-array start point
                sum = 0;

                for(int j=0;j<k;j++){ // make sub-array, and sub-array sum
                    sum +=A[i+j];
                    tempL[j] = A[i+j];
                }

                if(sum%2){ // test if it can be divided into two equal halves
                    test = false;
                    break;
                }else{
                    halfSum = sum/2;
                    
                    for(int ni=0;ni<k;ni++){
                        for(int j=halfSum;j>=ni;j--) testL[j] = testL[j] || testL[j-tempL[ni]];
                        /* cout << tempL[ni];
                        for(int j=0;j<=halfSum;j++) cout << ' ' << testL[j];
                        cout << '\n'; */
                        if(testL[halfSum]) break;
                    }
                    for(int j=1;j<halfSum;j++) testL[j] = false;
                    if(!testL[halfSum]){
                        test = false;
                        break;
                    }
                    testL[halfSum] = false;
                }
            }
            if(test){
                Klist[count] = k;
                count++;
            }
        }
        cout << count; // print answer
        for(int i=0;i<count;i++){
            cout << ' ' << Klist[i];
        }
        cout << '\n';
    }

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 340 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 360 KB Output is correct
2 Execution timed out 2029 ms 460 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2069 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -