제출 #1236759

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1236759		wedonttalkanymore	Kpart (eJOI21_kpart)	C++20	100 / 100	786 ms	892 KiB

Main

#include <bits/stdc++.h>
using namespace std;
int n, a[100005], pfs[100005], dp[100005], check[100005];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t; 
    cin >> t;
    while(t--){
        cin >> n;
        int sum = 0;
        for(int i = 1; i <= n; i++){
            cin >> a[i];
            check[i] = 1;
            sum += a[i];
            pfs[i] = pfs[i-1] + a[i];
        }
        for(int s = 0; s <= sum; s++) dp[s] = 0;
        for(int j = 1; j <= n; j++){
            for(int s = sum; s >= a[j]; s--) dp[s] = max(dp[s], dp[s - a[j]]);
            dp[a[j]] = j;
            for(int i = j; i >= 1; i--){
                int T = pfs[j] - pfs[i-1];
                int len = j - i + 1;
                if (T % 2 || dp[T/2] < i) check[len] = 0;
            }
        }
        vector<int> ans;
        for(int i = 1; i <= n; i++) if (check[i]) ans.push_back(i);
        cout << ans.size();
        for(int x: ans) cout << ' ' << x;
        cout << '\n';
    }
    return 0;
}

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