제출 #1163842

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1163842		kidkids	Kpart (eJOI21_kpart)	C++20	100 / 100	1079 ms	1000 KiB

Main

#include<bits/stdc++.h>

using namespace std;
const int maxn = 60001;
void solve() {
    int a;
    cin >> a;
    int carr[a + 10], arr[a + 10];
    carr[0] = 0;
    for (int i = 1;i <= a;i++) {
        cin >> arr[i];
        carr[i] = carr[i - 1] + arr[i];
    }
    int dp[maxn+10] = {},old[maxn+10] = {} , ans[a + 10] = {};
    // for(int j = 0;j<20;j++){
    //     cout<<j<<' ';
    // }
    // cout<<'\n';
    for (int i = 1;i <= a;i++) {
        old[0] = i;
        for (int j = 0;j + arr[i] <= maxn ;j++) {
            dp[j] = max(dp[j],old[j]);
            dp[j + arr[i]] = max(old[j],dp[j+arr[i]]);
            old[j] = dp[j];
        }
        for (int j = 1;j < i;j++) {
            int sum = carr[i] - carr[j-1];
            if (sum % 2 || old[sum / 2] < j) {
                ans[i - j + 1] = 1;
            }
        }
        // for (int j = 1;j < 8;j++) {
        //     cout<<ans[j]<<' ';
        // }
        // cout<<'\n';
        // for(int j = 0;j<20;j++){
        //     cout<<dp[j]<<' ';
        // }
        // cout<<'\n';
    }
    vector<int> v;
    for(int i = 2;i<=a;i++){
        if(!ans[i])
            v.push_back(i);
    }
    cout<<v.size()<<' ';
    for(auto p : v){
        cout<<p<<' ';
    }
    cout<<'\n';
}
int main() {
    int a;
    cin >> a;
    while (a--) {
        solve();
    }
}

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