Submission #1125911

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125911		_unknown_2010	Kpart (eJOI21_kpart)	C++20	10 / 100	2095 ms	544 KiB

Main

#ifndef LOCAL
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#endif

#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define vi vector
#define TESTCASES
const int mod = 1E9+7;
const int MAXN=200000;
const int inf=1e18;
void solution(){
    int n;
    cin >> n;
    vi<int> a(n);
    for(auto &x:a)cin >> x;
    vi<int> ans;
    for(int i=1; i<=n; i++){
        bool ok=1;
        for(int j=0; j<=n-i; j++){
            vi<int> vec;
            int sum=0;
            for(int k=j; k<j+i; k++){
                vec.push_back(a[k]);
                sum+=a[k];
            }
            vi<int> vis(sum+1);
            vis[0]=1;
            for(int k=0; k<vec.size(); k++){
                for(int j=sum-vec[k]; j>=0; j--){
                    if(vis[j]==0)continue;
                    vis[j+vec[k]]|=1;
                }
            }
            if(vis[sum/2]==0 || sum%2!=0){ok=0;break;}
        }
        if(ok)ans.push_back(i);
    }
    cout << ans.size() << ' ';
    for(auto &x:ans)cout << x << ' ';
}
int32_t main(){
    // clock_t tStart = clock();
    #ifdef khos
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int q = 1;
    #ifdef TESTCASES
       cin >> q;
    #endif
    while(q--) {
        solution();
        cout << '\n';
    }
    // cerr<<fixed<<setprecision(3)<<"\nTime Taken: "<<(double)(clock()- tStart)/CLOCKS_PER_SEC<<endl;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 70