oj.uz

Submission #1089417

# Submission time Handle Problem Language Result Execution time Memory
1089417 2024-09-16T12:50:36 Z vjudge1 Kpart (eJOI21_kpart) C++17
100 / 100
 1065 ms 1376 KB 
/*
	     author:khamzin
 	   Aibek aga is the best
	  created on 13.01.2024
	   20.10.2023 15:23:50
	   20.06.2024 16:38:22
                             		*/
#include <bits/stdc++.h>

#define EmirBey ios_base::sync_with_stdio(NULL);cin.tie(0);cout.tie(0);
#define fopen(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
#define all(x) (x).begin(), (x).end()
#define rb rbegin()
#define re rend()
#define len(x) (int)x.size()
#define sz size()
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define elif else if
#define F first
#define S second
#define int long long
#define pii pair<int,int>

using namespace std;

const int N = 1e6+234;
const int INF = (int)1e9 + 1;
const int maxn = 2e5;
const int mod = 1e9+7;

int n,a[N],pref[N],dp[N];

void putin()
{
    cin>>n;
    set<int>ans;
    for(int i=1 ; i<=n ; i++){
    	cin>>a[i];
    	ans.insert(i);
    	pref[i]=pref[i-1]+a[i];
    }
    for(int i=0 ; i<=pref[n] ; i++)dp[i]=0;
    for(int i=1 ; i<=n ; i++){
    	for(int j=pref[n] ; j>=a[i] ; j--){
    		dp[j]=max(dp[j],dp[j-a[i]]);
    	}
    	dp[a[i]]=i;
    	for(int j=1 ; j<=i-1 ; j++){
    		int sum=pref[i]-pref[j-1];
    		if(sum%2==1 || dp[sum/2]<j){
    			ans.erase(i-j+1);
    		}
    	}
    }
    ans.erase(1);
    cout<<ans.size()<<' ';
    for(auto it:ans){
    	cout<<it<<' ';
    }
    cout<<'\n';
}
signed main() {
       	int tt=1;
       	cin>>tt;
       	while(tt--){
       		putin();
       	} 
       	
        

}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 608 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 352 KB Output is correct
2 Correct 14 ms 348 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 604 KB Output is correct
2 Correct 153 ms 856 KB Output is correct
3 Correct 176 ms 860 KB Output is correct
4 Correct 333 ms 952 KB Output is correct
5 Correct 767 ms 1228 KB Output is correct
6 Correct 1065 ms 1364 KB Output is correct
7 Correct 954 ms 1376 KB Output is correct