Submission #829614

#	Time	Username	Problem	Language	Result	Execution time	Memory
829614		vuavisao	Kpart (eJOI21_kpart)	C++17	100 / 100	1567 ms	196064 KiB

Main

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

template<typename Lhs, typename Rhs> bool Min_self(Lhs& lhs, Rhs rhs) { if(rhs < lhs) { lhs = rhs; return true; } return false; } 
template<typename Lhs, typename Rhs> bool Max_self(Lhs& lhs, Rhs rhs) { if(rhs > lhs) { lhs = rhs; return true; } return false; } 


const int N = 1e3 + 10;

int n;
int a[N];
  
int cnt[N];
int dp[N][50010];

// 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 << ' ';
//         }
//     }
// }

void solve() {
    cin >> n;
    for(int i = 1; i <= n; ++ i) cin >> a[i];
    for(int i = 1; i <= n; ++ i) cnt[i] = 0; 
    for(int i = 0; i <= n; ++ i) {
        for(int j = 0; j <= 50000; ++ j) {
            dp[i][j] = 0;
        }
    }
    for(int i = 0; i < n; ++ i) {
        for(int s = 0; s <= 50000; ++ s) {
            if(s + a[i + 1] <= 50000) Max_self(dp[i + 1][s + a[i + 1]], (s == 0 ? i + 1 : dp[i][s]));
            Max_self(dp[i + 1][s], dp[i][s]);
        }
    }
    int res = 0;
    for(int i = 1; i <= n; ++ i) {
        int s = 0;
        for(int j = i; j <= n; ++ j) {
            s += a[j]; 
            if(s & 1) continue; 
            if(dp[j][s / 2] >= i) {
                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) {
        solve();
        cout << '\n';
    }
    return (0 ^ 0);
}

/// Code by vuavisao

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