oj.uz

Submission #593062

# Submission time Handle Problem Language Result Execution time Memory
593062 2022-07-10T10:21:41 Z Dextar Kpart (eJOI21_kpart) C++14
100 / 100
 1373 ms 195832 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 dp[1000][50002];


int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    for(int x=0; x<50002; x++) {
        dp[0][x] = -1;
    }
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        int a[n];
        for(int i=0; i<n; i++) {
            cin >> a[i];
        }
        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';
        dp[0][a[0]] = -1;
    }
    return 0;
}
/*
3
3 1 1
*/

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1748 KB Output is correct
2 Correct 18 ms 4076 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 14440 KB Output is correct
2 Correct 208 ms 31756 KB Output is correct
3 Correct 241 ms 40268 KB Output is correct
4 Correct 433 ms 66864 KB Output is correct
5 Correct 956 ms 162252 KB Output is correct
6 Correct 1373 ms 193116 KB Output is correct
7 Correct 1213 ms 195832 KB Output is correct