oj.uz

Submission #593058

# Submission time Handle Problem Language Result Execution time Memory
593058 2022-07-10T10:11:37 Z Dextar Kpart (eJOI21_kpart) C++14
30 / 100
 2000 ms 197000 KB 
#include <bits/stdc++.h>
#define first x
#define second y

using namespace std;

const int INF = 1000 * 1000 * 1000;
const int mod = 1000 * 1000 * 1000 + 7;

vector<vector<int>> dp(1000, vector<int>(50002));


int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    for(int i=0; i<1000; i++) {
        for(int j=0; j<50002; j++) {
            dp[i][j] = -1;
        }
    }
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for(int i=0; i<n; i++) {
            cin >> a[i];
        }
        vector<int> pref(n + 1);
        pref[0] = 0;
        for(int i=0; i<n; i++) {
            pref[i+1] = pref[i] + a[i];
        }
        int lim = (pref[n] >> 1) + 2;
        for(int i=0; i<n; i++) {
            for(int x=1; x<lim; x++) {
                if(x==a[i]) {
                    dp[i][x] = i;
                } else if(i>0)
                {
                    dp[i][x] = dp[i-1][x];
                    if(x-a[i]>0) {
                        dp[i][x] = max(dp[i][x], dp[i-1][x-a[i]]);
                    }
                }
            }
        }
        vector<int> ans;
        for(int k=2; k<=n; k++) {
            bool flag = true;
            for(int i=0; i+k<=n; i++) {
                int curSum = pref[i+k] - pref[i];
                if(curSum%2==1||dp[i+k-1][curSum>>1]<i) {
                    flag = false;
                    break;
                }
            }
            if(flag) {
                ans.push_back(k);
            }
        }
        cout << ans.size() << ' ';
        for(int k: ans) {
            cout << k << ' ';
        }
        cout << '\n';
        for(int i=0; i<n; i++) {
            for(int j=0; j<lim; j++) {
                dp[i][j] = -1;
            }
        }
    }
    return 0;
}
/*
3
3 1 1
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 196884 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 196836 KB Output is correct
2 Correct 146 ms 196816 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 196832 KB Output is correct
2 Correct 574 ms 196792 KB Output is correct
3 Correct 648 ms 196860 KB Output is correct
4 Correct 1086 ms 196960 KB Output is correct
5 Execution timed out 2081 ms 197000 KB Time limit exceeded
6 Halted 0 ms 0 KB -