oj.uz

Submission #602598

# Submission time Handle Problem Language Result Execution time Memory
602598 2022-07-23T09:17:16 Z dozer Kpart (eJOI21_kpart) C++14
10 / 100
 2000 ms 241012 KB 
#include <bits/stdc++.h>
using namespace std;
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define pb push_back
#define pii pair<int, int>
#define endl "\n"
#define sp " "
#define st first
#define nd second
#define N 200
#define modulo 1000000007


set<int> dp[N][N];
int arr[N], pre[N];

int main()
{
	fastio();

	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		for (int i = 1; i <= n; i++)
		{
			cin>>arr[i];
			pre[i] = pre[i - 1] + arr[i];
		}
		for (int i = 1; i <= n; i++)
		{
			for (int j = i; j <= n; j++)
				dp[i][j].clear();
		}
		for (int i = 1; i <= n; i++)
			dp[i][i].insert(arr[i]);

		for (int i = 1; i <= n; i++)
		{
			for (int j = i + 1; j <= n; j++)
			{
				for (auto k : dp[i][j - 1]) dp[i][j].insert(k), dp[i][j].insert(k + arr[j]);
				dp[i][j].insert(arr[j]);
			}
		}
		vector<int> ans;
		for (int i = 1; i <= n; i++)
		{
			int flag = 1;
			for (int j = 1; j <= n - i + 1; j++)
			{
				if ((pre[j + i - 1] - pre[j - 1]) % 2 == 1) flag = 0;
				if (dp[j][j + i - 1].count((pre[j + i - 1] - pre[j - 1]) / 2) == 0) flag = 0;
			}
			if (flag == 1) ans.pb(i);
		}
		cout<<ans.size()<<sp;
		for (auto i : ans) cout<<i<<sp;
		cout<<endl;
	}
	cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 403 ms 20400 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 4180 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -