제출 #1347740

#제출 시각아이디문제언어결과실행 시간메모리
1347740MuhammadSaramKpart (eJOI21_kpart)C++20
100 / 100
348 ms712 KiB
#include <bits/stdc++.h>

using namespace std;

#define endl '\n'

const int M = 5e4 + 1;

int mn[M];

void solve()
{
	int n;
	cin>>n;
	for (int i=0;i<M;i++) mn[i]=n;
	int a[n], pre[n+1]={};
	set<int> se;
	for (int i=0;i<n;i++)
		cin>>a[i], se.insert(i+1), pre[i+1]=pre[i]+a[i];
	for (int i=n-1;i>=0;i--)
	{
		mn[0]=i;
		for (int x=M-1-a[i];x>=0;x--)
			mn[x+a[i]]=min(mn[x+a[i]],mn[x]);
		for (int r=i;r<n;r++)
			if (pre[r+1]%2!=pre[i]%2 or mn[(pre[r+1]-pre[i])/2]>r)
				se.erase(r-i+1);
	}
	cout<<se.size()<<' ';
	for (int i:se)
		cout<<i<<' ';
	cout<<endl;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(NULL), cout.tie(NULL);

	int t;
	cin>>t;
	while (t--)
		solve();

	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...