Submission #1349946

#TimeUsernameProblemLanguageResultExecution timeMemory
1349946Jawad_Akbar_JJKpart (eJOI21_kpart)C++20
100 / 100
511 ms656 KiB
#include <iostream>
#include <vector>

using namespace std;
const int M = 50005;
int Mx[M], a[M];

int main(){
	int n, t;
	cin>>t;
	while (t--){
		cin>>n;

		for (int i=1;i<=n;i++)
			cin>>a[i];

		vector<int> ans;
		for (int j=1;j<M;j++)
			Mx[j] = -1;
		
		Mx[0] = 0;
		for (int i=1, s = 0;i<=n;i++){
			for (int j=min(M-1, a[i-1]);j+1;j--)
				if (j + a[i] < M and Mx[j] > Mx[j + a[i]])
					Mx[j+a[i]] = Mx[j];
			Mx[a[i]] = i;

			a[i] += a[i-1];
			for (int j=0;j<ans.size();j++){
				s = a[i] - a[i-ans[j]];
				if (s % 2 == 1 or Mx[s / 2] <= i - ans[j])
					ans.erase(ans.begin() + j), j--;
			}
			if (a[i] % 2 == 0 and Mx[a[i]/2] != -1)
				ans.push_back(i);
		}

		cout<<ans.size()<<' ';
		for (int i=0;i<ans.size();i++)
			cout<<ans[i]<<' ';
		cout<<'\n';
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...