제출 #630125

#제출 시각아이디문제언어결과실행 시간메모리
630125kidesoKpart (eJOI21_kpart)C++17
30 / 100
2093 ms627516 KiB
#include <iostream>
#include <queue>
#include <algorithm>

//#include <fstream>

using namespace std;

//ifstream F("be.txt");

vector<int> ans, x, s;
vector<vector<int> > dp;
int N;
const int maxN = 1e5;

int main(){
    int T;
    cin >> T;

    while(T--){
        ans.clear();

        cin >> N;
        x.assign(N + 1, 0);
        s.assign(N + 1, 0);

        for(int i = 1; i <= N; ++i){
            cin >> x[i];
            s[i] = s[i - 1] + x[i];
        }

        dp.assign(N + 1, vector<int> (s[N] + 1, 0));

        for(int i = 1; i <= N; ++i){
            for(int j = s[N]; j >= x[i]; --j)
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - x[i]]);
            
            dp[i][x[i]] = i;
            
            for(int j = x[i] - 1; j >= 0; --j)
                dp[i][j] = dp[i - 1][j];
        }

        bool ok;

        for(int i = 2; i <= N; ++i){
            ok = true;

            for(int j = 1; j <= N - i + 1; ++j){
                int sum = s[j + i - 1] - s[j - 1];
                if(sum % 2 || dp[j + i - 1][sum / 2] < j) ok = false;
            }

            if(ok) ans.push_back(i);
        }

        cout << ans.size() << ' ';
        for(auto e:ans)
            cout << e << ' ';
        cout << '\n';
    }

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...