oj.uz

Submission #593053

# Submission time Handle Problem Language Result Execution time Memory
593053 2022-07-10T09:56:34 Z Dextar Kpart (eJOI21_kpart) C++14
30 / 100
 2000 ms 161896 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;


int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    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];
        }
        vector<vector<int>> dp(n, vector<int>(pref[n] / 2 + 2, -1));
        for(int i=0; i<n; i++) {
            int lim = dp[0].size();
            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/2]<i) {
                    flag = false;
                    break;
                }
            }
            if(flag) {
                ans.push_back(k);
            }
        }
        cout << ans.size() << ' ';
        for(int k: ans) {
            cout << k << ' ';
        }
        cout << '\n';
    }
    return 0;
}
/*
3
3 1 1
*/

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1260 KB Output is correct
2 Correct 52 ms 3352 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 13268 KB Output is correct
2 Correct 624 ms 29712 KB Output is correct
3 Correct 706 ms 37836 KB Output is correct
4 Correct 1285 ms 64432 KB Output is correct
5 Execution timed out 2082 ms 161896 KB Time limit exceeded
6 Halted 0 ms 0 KB -