Submission #912587

#	Time	Username	Problem	Language	Result	Execution time	Memory
912587		andro	Kpart (eJOI21_kpart)	C++14	0 / 100	2062 ms	1052 KiB

Main

#include <bits/stdc++.h>

#define int long long

#define double long double

using namespace std;

const int N = 1e6;

bitset<N> dp;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while(t-- ) {
        int n;
        cin >> n;
        vector<int> a(n + 1);
        for(int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        vector<int> ans;
        vector<int> pref(n + 1);
        for(int i = 1; i <= n; i++) {
            pref[i] = pref[i - 1] + a[i];
        }
        for(int k = 1; k <= n; k++) {
            dp[0] = 1;
            for(int i = 1; i <= k; i++) {
                dp |= (dp << a[i]);
            }
            if(pref[k] % 2) {
                continue;
            }
            if(! dp[(pref[k]) / 2]) {
                continue;
            }
            int ok = 1;
            for(int i = k + 1; i <= n; i++) {
                dp &= (dp >> a[i - k]);
                dp[0] = 1;
                dp |= (dp << a[i]);
                if((pref[i] - pref[i - k]) % 2) {
                    ok = 0;
                    break;
                }
                if(! dp[(pref[i] - pref[i - k]) / 2]) {
                    ok = 0;
                    break;
                }
            }
            for(int i = 1; i <= n; i++) {
                dp &= (dp >> a[i]);
            }
            if(ok) {
                ans.push_back(k);
            }
        }
        cout << ans.size() << " ";
        for(auto it : ans) {
            cout << it << " ";
        }
        cout << "\n";
    }
}

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