제출 #1128214

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1128214		rasbery303	Kpart (eJOI21_kpart)	C++20	10 / 100	2093 ms	444 KiB

Main

#include <iostream>
#include <vector>
#include <deque>
using namespace std;

const int N = 1001;
int a[N];
vector<bool> dp;
deque<int> deq;

void solve(){
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    vector<int> pref(n+1, 0);
    for (int i = 1; i <= n; ++i)
        pref[i] = pref[i-1] + a[i];

    vector<int> ans;
    for (int len = 2; len <= n; ++len){
        bool add = true;
        bool in = false;

        for (int i = 0; i < len; ++i)
            deq.push_back(a[i]);

        for (int i = 1; i <= n-len+1 && add == true; ++i){
            deq.pop_front();
            deq.push_back(a[i+len-1]);

            int sum = pref[i+len-1] - pref[i-1];
            if (sum%2) break;
            in = true;

            dp.assign(sum+1, false);
            dp[0] = true;

            for (int x: deq)
                for (int val = sum/2; val >= x; --val)
                    dp[val] = dp[val] | dp[val-x];

            if (dp[sum/2] == 0)
                add = false;
        }
        if (add && in)
            ans.push_back(len);
        
        deq.clear();
    }
    cout << ans.size() << ' ';
    for (int i = 0; i < ans.size(); ++i)
        cout << ans[i] << " \n"[i==ans.size()-1];
}

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

    int tt;
    cin >> tt;
    while(tt--)
        solve();
    return 0;
}

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