oj.uz

답안 #638235

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
638235 2022-09-05T04:51:32 Z Tekor Kpart (eJOI21_kpart) C++17
30 / 100
 2000 ms 992 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define all(v) v.begin(),v.end()
#define en '\n'
void boos() {
	ios_base :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}
const int N = 1e3 + 100,M = 1e5 + 10;
int n,cnt[N],dp[M],a[N],pr[N];
void solve() {
	int m = 0;
	cin >> n;
	for(int i = 1;i <= n;i++) {
		cin >> a[i];
		m += a[i];
		pr[i] = m;
		cnt[i] = 0;
	}
	for(int i = 0;i <= m;i++)dp[i] = n + 1;
	for(int i = n;i >= 1;i--) {
		dp[0] = i;
		for(int j = m;j >= 1;j--) {
			if(j >= a[i])dp[j] = min(dp[j],dp[j - a[i]]);
			if(dp[j] != n + 1 && j % 2 == 0 && dp[j / 2] <= dp[j] && j == pr[dp[j]] - pr[i - 1])cnt[dp[j] - i + 1]++;
			//cout << dp[j] << " ";
		}
		//cout << en;
		//cout << cnt[4] << " " << cnt[6] << en;
	}
	vector <int> ans;
	for(int i = 2;i <= n;i++) {
		if(cnt[i] == n - i + 1)ans.pb(i);
	}
	cout << ans.size() << " ";
	for(auto to : ans)cout << to << " ";
	cout << en;
}
int main() {
	boos();
	int ttt;
	cin >> ttt;
	while(ttt--)solve();
}

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 372 KB Output is correct
2 Correct 38 ms 380 KB Output is correct

Subtask #3
0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 149 ms 440 KB Output is correct
2 Correct 407 ms 512 KB Output is correct
3 Correct 447 ms 616 KB Output is correct
4 Correct 821 ms 704 KB Output is correct
5 Correct 1846 ms 964 KB Output is correct
6 Execution timed out 2086 ms 992 KB Time limit exceeded
7 Halted 0 ms 0 KB -