Submission #829583

#	Time	Username	Problem	Language	Result	Execution time	Memory
829583		vuavisao	Kpart (eJOI21_kpart)	C++17	30 / 100	749 ms	352 KiB

Main

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define ll long long
using namespace std;

const int N = 1e3 + 10;

int n;
int a[N];

namespace sub2 {
    bitset<100010> bs;
    int cnt[122];

    void solve() {
        cin >> n;
        for(int i = 1; i <= n; ++ i) cin >> a[i]; 
        for(int i = 1; i <= n; ++ i) cnt[i] = 0;
        int res = 0;
        for(int i = 1; i <= n; ++ i) {
            int s = 0;
            bs.reset(); bs.set(0);
            for(int j = i; j <= n; ++ j) {
                s += a[j];
                bs |= bs << a[j];
                if(s & 1) continue;
                if(bs[s / 2] == true) {
                    if(++ cnt[j - i + 1] == n - (j - i + 1) + 1) ++ res;
                }
            }
        }
        cout << res << ' ';
        for(int i = 2; i <= n; ++ i) {
            if(cnt[i] == n - i + 1) cout << i << ' ';
        }
    }
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int t; cin >> t;
    while(t-- > 0) {
        sub2::solve();
        cout << '\n';
    }
    return (0 ^ 0);
}

/// Code by vuavisao

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