oj.uz

Submission #630135

# Submission time Handle Problem Language Result Execution time Memory
630135 2022-08-15T17:56:00 Z kideso Kpart (eJOI21_kpart) C++17
100 / 100
 1882 ms 391896 KB 
#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

vector<int> ans;
int N;
int x[1001], s[1001], dp[1001][100001];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T;
    cin >> T;
    
    while(T--){
        ans.clear();

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

        for(int j = 0; j <= s[N]; ++j)
            dp[0][j] = 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;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 852 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2644 KB Output is correct
2 Correct 28 ms 7108 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 27368 KB Output is correct
2 Correct 285 ms 61544 KB Output is correct
3 Correct 346 ms 78452 KB Output is correct
4 Correct 612 ms 130968 KB Output is correct
5 Correct 1352 ms 321132 KB Output is correct
6 Correct 1882 ms 385880 KB Output is correct
7 Correct 1768 ms 391896 KB Output is correct