Submission #593048

#	Time	Username	Problem	Language	Result	Execution time	Memory
593048		Dextar	Kpart (eJOI21_kpart)	C++14	30 / 100	2041 ms	161816 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 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);
        pref[0] = a[0];
        for(int i=1; i<n; i++) {
            pref[i] = pref[i-1] + a[i];
        }
        vector<vector<int>> dp(n, vector<int>(pref[n-1] / 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-1];
                if(i>0) {
                    curSum -= pref[i-1];
                }
                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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 70