oj.uz

Submission #1107556

# Submission time Handle Problem Language Result Execution time Memory
1107556 2024-11-01T13:07:31 Z vjudge1 Kpart (eJOI21_kpart) C++17
100 / 100
 1047 ms 1352 KB 
#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.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 1104 KB Output is correct
2 Correct 127 ms 1104 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 1104 KB Output is correct
2 Correct 404 ms 1104 KB Output is correct
3 Correct 427 ms 1352 KB Output is correct
4 Correct 589 ms 1104 KB Output is correct
5 Correct 847 ms 1292 KB Output is correct
6 Correct 1047 ms 1296 KB Output is correct
7 Correct 1018 ms 1288 KB Output is correct