제출 #1150863

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1150863		somefolk	Kpart (eJOI21_kpart)	C++20	100 / 100	789 ms	872 KiB

Main

#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <unordered_set>
#include <complex>
#include <list>
#include <cassert>
#include <chrono>
#include <random>
#include <stack>
#include <iomanip>
#include <fstream>
using namespace std;

#define endl "\n"
// #define int long long

const int INF = 2 * 1e5 + 5;
const int MOD = 1e9 + 7;

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

    vector<int> dp(pref[n], 0), good(n+1, 1);
    for(int i = 1; i <= n; i++){
        for(int j = pref[n]; j >= a[i]; j--){
            dp[j] = max(dp[j], dp[j-a[i]]);
        }
        dp[a[i]] = i;
        for(int k = 2; k <= i; k++){
            int sum = pref[i] - pref[i-k];
            if(sum%2==1 || dp[sum/2] < i-k+1){
                good[k] = 0;
            }
        }
    }

    vector<int> sol;
    for(int i = 2; i <= n; i++){
        if(good[i]){
            sol.push_back(i);
        }
    }

    sort(sol.begin(), sol.end());

    cout << sol.size() << " ";
    for(auto &i : sol){
        cout << i << " ";
    }
    cout << endl;
}

int32_t main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int t = 1;
    cin >> t;
    while(t--) solve();
    return 0;
}

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