Submission #905146

#	Time	Username	Problem	Language	Result	Execution time	Memory
905146		penguin133	Kpart (eJOI21_kpart)	C++17	30 / 100	2017 ms	685884 KiB

Main

#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[1005][100005];
int n, A[1005];
void solve(){
	cin >> n;
	int sm = 0;
	for(int i=1;i<=n;i++)cin >> A[i], sm += A[i];
	dp[0][0] = {1, n + 1};
	for(int i=1;i<=n;i++){
		for(int j=0;j<=sm;j++){
			dp[i][j] = dp[i-1][j];
			if(j >= A[i]){
				if(dp[i - 1][j - A[i]].fi){
					int mn = min(dp[i - 1][j - A[i]].se, i);
					if(dp[i][j].fi)dp[i][j].se = max(dp[i][j].se, mn);
					else dp[i][j].se = mn;
					dp[i][j].fi = 1;
				}
			}
		}
	}
	vector <int> pos;
	for(int i=1;i<=n;i++){
		bool f = 1;
		sm = 0;
		//cerr << i << '\n';
		for(int j=1;j<i;j++)sm += A[j];
		for(int j=i;j<=n;j++){
			sm += A[j] - A[j - i];
			//cerr << j << ' ' << '\n';
			if(sm%2 == 0 && dp[j][sm / 2].fi && dp[j][sm / 2].se >= j - i + 1){}
			else f = 0;
		}
		if(f)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 (stderr)

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

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 70