oj.uz

Submission #1107324

# Submission time Handle Problem Language Result Execution time Memory
1107324 2024-11-01T06:15:52 Z vjudge1 Kpart (eJOI21_kpart) C++17
10 / 100
 2000 ms 2488 KB 
#include <bits/stdc++.h>

using namespace std;

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

const int N = 1001;
int ans[N], a[N], p[N];

void solve()
{
	int n;
	cin >>n;
	int a[n + 1], p[n + 1];
	for( int i = 1; i <= n; ++i )
	{
		cin >>a[i];
		p[i] = p[i - 1] + a[i];
	}
	for( int i = 1; i <= n; ++i )
	{
		map<int, bool>sums;
		sums[0] = true;
		for( int j = i; j <= n; ++j )
		{
			vector< int >s;
			for( auto [x, c]: sums )
				s.pb( x );
			for( int k: s )
				sums[k + a[j]] = true;
			int sum = p[j] - p[i - 1];
			if( sum & 1 )
				continue;
			if( sums.count(sum / 2) )
				ans[j - i + 1]++;
		}
	}
	vector< int >v;
	for( int i = 1; i <= n; ++i )
	{
		if( ans[i] == n - i + 1 )
			v.pb( i );
		ans[i] = 0;
	}
	cout <<sz(v) <<' ';
	for( int i: v )
		cout <<i <<' ';
	cout <<nl;
}

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 137 ms 696 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2061 ms 1012 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2041 ms 2488 KB Time limit exceeded
2 Halted 0 ms 0 KB -