Submission #834161

#	Time	Username	Problem	Language	Result	Execution time	Memory
834161		Knight	Kpart (eJOI21_kpart)	C++14	10 / 100	2069 ms	460 KiB

Main

#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 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 70