Submission #1155399

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155399		andrei_n	Kpart (eJOI21_kpart)	C++20	100 / 100	730 ms	880 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int INF = 999999999;

int v[1005];
int fr[1005];
int dp[2][50005];

signed main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T; cin>>T; while(T--)
    {
        int n; cin>>n;
        for(int i=1; i<=n; ++i)
        {
            cin>>v[i];
            fr[i] = 0;
        }
        for(int i=0; i<50005; ++i)
            dp[0][i] = dp[1][i] = INF;
        dp[n%2][0] = n;
        dp[n%2][v[n]] = n;
        for(int i=n-1; i>=1; --i)
        {
            int l1 = (i%2), l2 = (i+1)%2;
            for(int j=1; j<=50000; ++j)
            {
                dp[l1][j] = dp[l2][j];
                if(j >= v[i]) dp[l1][j] = min(dp[l1][j], dp[l2][j - v[i]]);
            }
            dp[l1][0] = i;
            dp[l1][v[i]] = i;
            int sum = 0;
            for(int j=i; j<=n; ++j)
            {
                sum += v[j];
                if(sum % 2 == 0 && dp[l1][sum/2] <= j)
                    ++fr[j-i+1];
            }
        }
        vector<int> res;
        for(int i=1; i<=n; ++i)
            if(fr[i] == n-i+1)
                res.push_back(i);
        cout<<res.size();
        for(auto &i : res) cout<<' '<<i;
        cout<<'\n';
    }
    return 0;
}

/*
2
7
7 3 5 1 3 3 5
6
1 2 3 5 8 3
*/

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70