oj.uz

Submission #1089456

# Submission time Handle Problem Language Result Execution time Memory
1089456 2024-09-16T14:28:09 Z vjudge1 Kpart (eJOI21_kpart) C++17
100 / 100
 1120 ms 1552 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include <sstream>
using namespace std;
#define accepted ios_base::sync_with_stdio(0);cin.tie(0);
#define Daulbekov signed
#define Makan main
#define int long long
#define double long double
#define pb push_back
#define F first
#define S second
const long long N=5e5+10;
const long long MOD=1e9+7;
const long long INF=2e18;
int binpow(int a,int b){
	a%=MOD;
	if(b==0)return 1;
	if(b%2)return binpow(a,b-1)*a%MOD;
	else {
		int res=binpow(a,b/2);
		return res*res%MOD;
	}
}
bool cmp(pair<pair<int,int>,int>a,pair<pair<int,int>,int>b){
	if(a.F.F/300!=b.F.F/300)return a.F.F/300<b.F.F/300;
	return a.F.S<b.F.S;
}
int dp[100005],a[1005],pref[1005],ans[1005];
Daulbekov Makan(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	accepted
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		pref[0]=0;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			ans[i]=1;
			pref[i]=pref[i-1]+a[i];
		}
		for(int i=1;i<=n;i++){
			for(int x=100000;x>=a[i];x--){
				dp[x]=max(dp[x],dp[x-a[i]]);
			}
			dp[a[i]]=i;
			for(int k=2;k<=i;k++){
				int sum=pref[i]-pref[i-k];
				if(sum%2==0&&i-k+1<=dp[sum/2]);
				else ans[k]=0;
			}
		}
		int cnt=0;
		for(int i=2;i<=n;i++)cnt+=ans[i];
		cout<<cnt<<" ";
		for(int i=2;i<=n;i++)if(ans[i]==1)cout<<i<<" ";
		cout<<"\n";
		for(int i=1;i<=100000;i++)dp[i]=0;
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1252 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 1232 KB Output is correct
2 Correct 127 ms 1128 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 1116 KB Output is correct
2 Correct 435 ms 1260 KB Output is correct
3 Correct 438 ms 1276 KB Output is correct
4 Correct 605 ms 1236 KB Output is correct
5 Correct 890 ms 1544 KB Output is correct
6 Correct 1120 ms 1116 KB Output is correct
7 Correct 1018 ms 1552 KB Output is correct