oj.uz

Submission #1106405

# Submission time Handle Problem Language Result Execution time Memory
1106405 2024-10-30T09:22:49 Z Muhammet Kpart (eJOI21_kpart) C++17
100 / 100
 1794 ms 1228 KB 
#include "bits/stdc++.h"

using namespace std;

#define ll long long
#define ff first
#define ss second

const int N = 3e5+5;

int T, n;

int main(){
	cin >> T;
	while(T--){
		cin >> n;
		vector <int> a(n+1);
		int s1 = 0;
		for(int i = 1; i <= n; i++){
			cin >> a[i];
			s1 += a[i];
		}
		vector <bool> vis(n+1,0);
		vector <int> dp(s1+1,0), dp1(s1+1,0);
		for(int i = 1; i <= n; i++){
			dp1[a[i]] = i;
			for(int j = a[i]; j <= s1; j++){
				dp1[j] = max(dp1[j], dp[j - a[i]]);
			}
			int s = 0;
			// cout << i << "\n";
			for(int j = i; j >= 1; j--){
				s += a[j];
				// cout << j << " " << s << ' ' << dp[s/2] << "\n";
				if(dp[s/2] < j or s % 2 == 1) vis[i-j+1] = 1;
			}
			dp = dp1;
		}
		vector <int> v;
		int cnt = 0;
		for(int i = 1; i <= n; i++){
			if(vis[i] == 0){
				cnt++;
				v.push_back(i);
			}
		}
		cout << cnt << ' ';
		for(auto i : v){
			cout << i << " ";
		}
		cout << '\n';
	}
}

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 348 KB Output is correct
2 Correct 23 ms 336 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 592 KB Output is correct
2 Correct 266 ms 864 KB Output is correct
3 Correct 295 ms 856 KB Output is correct
4 Correct 555 ms 876 KB Output is correct
5 Correct 1262 ms 1168 KB Output is correct
6 Correct 1794 ms 1228 KB Output is correct
7 Correct 1580 ms 1220 KB Output is correct