Submission #602866

#	Time	Username	Problem	Language	Result	Execution time	Memory
602866		dozer	Kpart (eJOI21_kpart)	C++14	100 / 100	1867 ms	391744 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define pb push_back
#define pii pair<int, int>
#define endl "\n"
#define sp " "
#define st first
#define nd second
#define N 1005
#define M 100005
#define modulo 1000000007


int dp[N][M];
int arr[N], pre[N];

int main()
{
	fastio();

	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		for (int i = 1; i <= n; i++)
		{
			cin>>arr[i];
			pre[i] = pre[i - 1] + arr[i];
		}

		for (int i = 0; i <= pre[n]; i++)
			dp[0][i] = 0;
		for (int i = 1; i <= n; i++)
		{
			for (int j = pre[n] - arr[i]; j > 0; j--)
			{
				dp[i][j + arr[i]] =  max(dp[i - 1][j + arr[i]], dp[i - 1][j]);
			}
			dp[i][arr[i]] = i;
			for (int j = arr[i] - 1; j > 0; j--) dp[i][j] = dp[i - 1][j];
		}

		vector<int> ans;
		for (int i = 2; i <= n; i++)
		{
			int flag = 1;
			for (int j = 1; j <= n - i + 1; j++)
			{
				int sum = pre[j + i - 1] - pre[j - 1];
				if (sum % 2 == 1 || dp[j + i - 1][sum / 2] < j) flag = 0;
				//if (sum % 2 == 0) cout<<j + i - 1<<sp<<sum / 2<<sp<<dp[j + i - 1][sum / 2]<<endl;
			}
			if (flag == 1) ans.pb(i);
		}
		cout<<ans.size()<<sp;
		for (auto i : ans) cout<<i<<sp;
		cout<<endl;
	}
	cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
}

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