oj.uz

Submission #840921

# Submission time Handle Problem Language Result Execution time Memory
840921 2023-08-31T22:58:12 Z pera Kpart (eJOI21_kpart) C++17
30 / 100
 2000 ms 193924 KB 
#include<bits/stdc++.h>
using namespace std;

//#define int long long

const int N = 2e5 + 1;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int t = 1;cin >> t;
	while(t --){
		int n;cin >> n;
		vector<int> a(n + 1) , p(n + 1) , ls(n + 1) , ans;
		for(int i = 1;i <= n;i ++){
			cin >> a[i];
			p[i] = p[i - 1] + a[i];
			ls[i] = 1;
		}
		int X = p[n] / 2;
		vector<vector<int>> dp(n + 1 , vector<int>(X));
		for(int i = 1;i <= n;i ++){
			dp[i] = dp[i - 1];
			dp[i][a[i]] = i;
			for(int j = X;j > a[i];j --){
				dp[i][j] = max(dp[i][j] , dp[i - 1][j - a[i]]);
			}
		}
		for(int i = 1;i <= n;i ++){
			for(int j = i;j <= n;j ++){
				ls[j - i + 1] &= ((p[j] - p[i - 1]) % 2 == 0 && dp[j][(p[j] - p[i - 1]) / 2] >= i);
			}
		}
		cout << accumulate(ls.begin() , ls.end() , 0) << endl;
		for(int i = 1;i <= n;i ++){
			if(ls[i] == 1) cout << i << " ";
		}
		cout << endl;
	}
}

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1220 KB Output is correct
2 Correct 23 ms 3432 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 13344 KB Output is correct
2 Correct 330 ms 29740 KB Output is correct
3 Correct 387 ms 37912 KB Output is correct
4 Correct 732 ms 64492 KB Output is correct
5 Correct 1572 ms 161996 KB Output is correct
6 Execution timed out 2072 ms 193924 KB Time limit exceeded
7 Halted 0 ms 0 KB -