oj.uz

Submission #829614

# Submission time Handle Problem Language Result Execution time Memory
829614 2023-08-18T13:21:58 Z vuavisao Kpart (eJOI21_kpart) C++17
100 / 100
 1567 ms 196064 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 6356 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 13628 KB Output is correct
2 Correct 206 ms 23428 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 513 ms 50628 KB Output is correct
2 Correct 837 ms 75516 KB Output is correct
3 Correct 677 ms 85296 KB Output is correct
4 Correct 887 ms 110896 KB Output is correct
5 Correct 1317 ms 171656 KB Output is correct
6 Correct 1567 ms 193200 KB Output is correct
7 Correct 1473 ms 196064 KB Output is correct