oj.uz

Submission #1100864

# Submission time Handle Problem Language Result Execution time Memory
1100864 2024-10-14T20:34:49 Z Acanikolic Kpart (eJOI21_kpart) C++14
100 / 100
 1829 ms 1408 KB 
#include <bits/stdc++.h>  

#define pb push_back
 
#define F first
 
#define S second
 
using namespace std;
 
const int N = 1e5 + 10;
 
const int mod = 1e9 + 7;
 
const long long inf = 1e14;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 	
 	int tt;
 	cin >> tt;
 	while(tt--) {
 		int n;
 		cin >> n;
 		vector<int>a(n + 1),pref(n + 1);
 		for(int i = 1; i <= n; i++) {
 			cin >> a[i];
 			pref[i] = pref[i - 1] + a[i];
 		}
 		int mx = pref[n];
 		vector<bool>valid(n + 1,true);
 		vector<int>dp(mx + 1);
 		for(int i = 1; i <= n; i++) {
 			vector<int>new_dp = dp;
 			for(int j = a[i]; j <= mx; j++) {
 				new_dp[j] = max(new_dp[j],dp[j - a[i]]);
 			} 
 			new_dp[a[i]] = i;
 			dp = new_dp;
 			for(int j = i - 1; j >= 1; j--) {
 				int sum = pref[i] - pref[j - 1];
 				if(sum & 1 || dp[sum / 2] < j) valid[i - j + 1] = false;
 			}
 		}
 		vector<int>ans;
 		for(int i = 2; i <= n; i++) if(valid[i]) ans.pb(i);
 		cout << ans.size() << " ";
 		for(auto X : ans) cout << X << " ";
 		cout << "\n";
 	}
    return 0;
}

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 548 KB Output is correct
2 Correct 23 ms 592 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 756 KB Output is correct
2 Correct 275 ms 764 KB Output is correct
3 Correct 327 ms 900 KB Output is correct
4 Correct 556 ms 1028 KB Output is correct
5 Correct 1293 ms 1304 KB Output is correct
6 Correct 1829 ms 1336 KB Output is correct
7 Correct 1660 ms 1408 KB Output is correct