oj.uz

Submission #537799

# Submission time Handle Problem Language Result Execution time Memory
537799 2022-03-15T14:13:10 Z hmm789 Kpart (eJOI21_kpart) C++14
100 / 100
 1656 ms 193320 KB 
#include <bits/stdc++.h>
using namespace std;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t;
	cin >> t;
	while(t--) {
		int n, sm;
		cin >> n;
		int a[n], pref[n+1];
		for(int i = 0; i < n; i++) cin >> a[i];
		pref[0] = 0;
		for(int i = 0; i < n; i++) pref[i+1] = pref[i] + a[i];
		sm = pref[n]/2;
		vector<int> ans;
		int dp[n][sm+1];
		for(int i = 0; i < n; i++) {
			for(int j = 0; j <= sm; j++) {
				if(j == 0) dp[i][j] = i;
				else if(i == 0 && j == a[0]) dp[i][j] = i;
				else if(i == 0) dp[i][j] = -1;
				else if(j < a[i]) dp[i][j] = dp[i-1][j];
				else dp[i][j] = max(dp[i-1][j], dp[i-1][j-a[i]]);
			}
		}
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n-i; j++) {
				sm = pref[j+i+1] - pref[j];
				if(sm % 2 == 1 || dp[j+i][sm/2] < j) goto ed;
			}
			ans.push_back(i+1);
			ed:;
		}
		cout << ans.size() << " ";
		for(int i : ans) cout << i << " ";
		cout << '\n';
	}
}

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1216 KB Output is correct
2 Correct 20 ms 3412 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 13112 KB Output is correct
2 Correct 248 ms 29652 KB Output is correct
3 Correct 293 ms 37760 KB Output is correct
4 Correct 503 ms 64396 KB Output is correct
5 Correct 1219 ms 158828 KB Output is correct
6 Correct 1656 ms 192256 KB Output is correct
7 Correct 1474 ms 193320 KB Output is correct