oj.uz

Submission #905156

# Submission time Handle Problem Language Result Execution time Memory
905156 2024-01-12T16:32:13 Z penguin133 Kpart (eJOI21_kpart) C++17
100 / 100
 1685 ms 2280 KB 
#include <bits/stdc++.h>
using namespace std;

//#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

pair <bool, int> dp[2][100005];
int n, A[1005], bruh[1005], P[1005];
void solve(){
	cin >> n;
	int sm = 0;
	for(int i=1;i<=n;i++)cin >> A[i], sm += A[i], P[i] = P[i-1] + A[i], bruh[i] = 1;
	for(int i = 0; i <= sm; i++)dp[0][i] = dp[1][i] = {0, 0};
	dp[0][0] = {1, n + 1};
	for(int i=1;i<=n;i++){
		int x = i & 1;
		for(int j=0;j<=P[i];j++){
			dp[x][j] = dp[x^1][j];
			if(j >= A[i]){
				if(dp[x^1][j - A[i]].fi){
					int mn = min(dp[x ^ 1][j - A[i]].se, i);
					if(dp[x][j].fi)dp[x][j].se = max(dp[x][j].se, mn);
					else dp[x][j].se = mn;
					dp[x][j].fi = 1;
				}
			}
		}
		for(int j = 1; j <= i; j++){
			if((P[i] - P[i - j]) % 2)bruh[j] = 0;
			if(!dp[x][(P[i] - P[i - j]) / 2].fi)bruh[j] = 0;
			if(dp[x][(P[i] - P[i - j]) / 2].se <= i - j)bruh[j] = 0;
		}
	}
	vector <int> pos;
	for(int i=1;i<=n;i++){
		if(bruh[i])pos.push_back(i);
	}
	cout << (int)pos.size() << ' ';
	for(auto i : pos)cout << i << ' ';
	cout << '\n';
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message

Main.cpp:50:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   50 | main(){
      | ^~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 604 KB Output is correct
2 Correct 24 ms 604 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 860 KB Output is correct
2 Correct 255 ms 1104 KB Output is correct
3 Correct 277 ms 1180 KB Output is correct
4 Correct 541 ms 1620 KB Output is correct
5 Correct 1176 ms 1928 KB Output is correct
6 Correct 1685 ms 2280 KB Output is correct
7 Correct 1462 ms 2272 KB Output is correct