Submission #1107556

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107556		vjudge1	Kpart (eJOI21_kpart)	C++17	100 / 100	1047 ms	1352 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define nl '\n'
#define pb push_back
#define sz(x) x.size()

const int N = 1001;
const int N1 = 1e5 + 1;
int n, a[N], p[N], dp[N1], bad[N];

void solve()
{
    cin >>n;
    for( int i = 1; i <= n; ++i )
    {
        cin >>a[i];
        p[i] = p[i - 1] + a[i];
    }
    for( int i = 1; i <= n; ++i )
    {
        for( int x = N1 - 1; x > a[i]; --x )
            dp[x] = max(dp[x], dp[x - a[i]]);
        dp[a[i]] = i;
        for( int j = 1; j <= i; ++j )
        {
            int sum = p[i] - p[j - 1];
            if( sum & 1 || dp[sum / 2] < j )
                bad[i - j + 1] = 1;
        }
    }
    vector< int >ans;
    for( int i = 1; i <= n; ++i )
    {
        if( !bad[i] )
            ans.pb( i );
        bad[i] = 0;
    }
    cout <<sz(ans) <<' ';
    for( int i: ans )
        cout <<i <<' ';
    cout <<nl;
    for( int i = 0; i < N1; ++i )
        dp[i] = 0;
}


signed main() 
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    int T = 1;
    cin >>T;
    while( T-- )
        solve();
}

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