oj.uz

Submission #580876

# Submission time Handle Problem Language Result Execution time Memory
580876 2022-06-22T04:23:03 Z penguin133 Kpart (eJOI21_kpart) C++14
30 / 100
 2000 ms 1400 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pi pair<int, int> 
#define pii pair<int, pair<int, int> >
int P[200005], P2[200005], A[200005], S[200005];
int n;
bool dp[2][100005];
bool X[1005][1005];
void solve(){
	memset(X, 0, sizeof(X));
	cin >> n;
	int ans = 0;
	for(int i=1;i<=n;i++)cin >> A[i], ans += A[i], P[i] = P[i-1] + A[i];
	for(int i=1;i<=n;i++){
		for(int j=0;j<=1;j++)for(int k=0;k<=ans;k++)dp[j][k] = 0;
		dp[(i-1)%2][0] = 1;
		for(int j=i;j<=n;j++){
			int x = j % 2;
			for(int k=0;k<=ans;k++){
				if(k >= A[j])dp[x][k] = (dp[1-x][k-A[j]] | dp[1-x][k]);
				else dp[x][k] = dp[1-x][k];
			}
			if((P[j]  - P[i-1])%2 == 0 && dp[j%2][(P[j] - P[i-1])/2])X[i][j] = 1;
		}
	}
	vector<int>v;
	for(int i=1;i<=n;i++){
		int flag = 1;
		for(int j=1;j<=n-i+1;j++)if(!X[j][j+i-1])flag = 0;
		if(flag)v.push_back(i);
	}
	cout << v.size() << " ";
	for(auto i : v)cout << i << " ";
	cout << '\n';
	
}
main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int t = 1;
	cin >> t;
	while(t--){
		solve();
	}
}

Compilation message

Main.cpp:40:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   40 | main(){
      | ^~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 1340 KB Output is correct
2 Correct 1004 ms 1364 KB Output is correct

Subtask #3
0 / 70.0

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