Submission #593062

#	Time	Username	Problem	Language	Result	Execution time	Memory
593062		Dextar	Kpart (eJOI21_kpart)	C++14	100 / 100	1373 ms	195832 KiB

Main

#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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70