oj.uz

Submission #829583

# Submission time Handle Problem Language Result Execution time Memory
829583 2023-08-18T13:05:13 Z vuavisao Kpart (eJOI21_kpart) C++17
30 / 100
 749 ms 352 KB 
#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.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 340 KB Output is correct
2 Correct 166 ms 348 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 749 ms 352 KB Output isn't correct
2 Halted 0 ms 0 KB -