Submission #1116164

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116164		Nuraly_Serikbay	Kpart (eJOI21_kpart)	C++17	100 / 100	1176 ms	2832 KiB

Main

//#pragma GCC optimize(" unroll-loops")
//#pragma gcc optimize("Ofast")
//#pragma GCC optimization("Ofast")
//#pragma optimize(Ofast)
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <fstream>
#include <unordered_map>
using namespace std;

typedef long long ll;
typedef long double ld;

#define all(x) x.begin(),x.end()
#define pb push_back
#define ent "\n"

#define int long long

const int maxn = (int)1e5 + 1;
const ll inf = (long long)1e9+ 20;
const int mod = (int)1e9 + 7;

int gcd(int x,int y){while(1){if(x > y)swap(x,y);if(!x)return y;y %= x;}}

int n;
int a[maxn];
int pref[maxn];
int dp[maxn * 2];

void solve(){
	cin >> n;
	set<int>s;
	for(int i = 1 ; i <= maxn ; i ++)dp[i] = 0;
	for(int i = 1 ; i <= n ; i ++){
		cin >> a[i];
		pref[i] = pref[i - 1] + a[i];
		s.insert(i);
	}
	s.erase(1);
	for(int i = 1 ; i <= n ; i ++){
		for(int j = maxn ; j > a[i] ; j --){
			dp[j] = max(dp[j],dp[j - a[i]]);
		}
		dp[a[i]] = i;
		for(int j = 2 ; j <= i ; j ++){
			int sum = pref[i] - pref[i - j];
			if(sum % 2 || dp[sum / 2] < i - j + 1){
				//cout << i << ' ' << j << ent;
				s.erase(j);
			}
		}
	}
	cout << s.size() << ' ';
	for(int to : s){
		cout << to << ' ';
	}
	cout << ent;
}

signed main(){
	// freopen("ones.in" , "r" , stdin) ;
	// freopen("ones.out" , "w" , stdout) ;
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	 cin >> t;
	while(t --){
		solve();
	}
	return 0;
}

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