oj.uz

답안 #537488

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
537488 2022-03-15T07:15:09 Z hmm789 Kpart (eJOI21_kpart) C++14
30 / 100
 2000 ms 782296 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;
		cin >> n;
		int a[n], pref[n+1], sm;
		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;
		bool dp[n][n][sm+1];
		for(int i = 0; i < n; i++) {
			for(int j = 0; j <= sm; j++) {
				if(j == 0 || j == a[i]) dp[i][i][j] = 1;
				else dp[i][i][j] = 0;
			}
			for(int j = i+1; j < n; j++) {
				for(int k = 0; k <= sm; k++) {
					if(dp[i][j-1][k] == 1 || (a[j] <= k && dp[i][j-1][k-a[j]] == 1)) dp[i][j][k] = 1;
					else dp[i][j][k] = 0;
				}
			}
		}
		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][j+i][sm/2] == 0) {
					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

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 1492 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 114 ms 16320 KB Output is correct
2 Correct 693 ms 89760 KB Output is correct

Subtask #3
0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2117 ms 782296 KB Time limit exceeded
2 Halted 0 ms 0 KB -