oj.uz

Submission #1116164

# Submission time Handle Problem Language Result Execution time Memory
1116164 2024-11-21T09:46:50 Z Nuraly_Serikbay Kpart (eJOI21_kpart) C++17
100 / 100
 1176 ms 2832 KB 
//#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2640 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 2640 KB Output is correct
2 Correct 127 ms 2640 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 2640 KB Output is correct
2 Correct 437 ms 2640 KB Output is correct
3 Correct 448 ms 2640 KB Output is correct
4 Correct 632 ms 2756 KB Output is correct
5 Correct 911 ms 2748 KB Output is correct
6 Correct 1176 ms 2788 KB Output is correct
7 Correct 1073 ms 2832 KB Output is correct