Submission #1155432

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155432		Ciprian	Kpart (eJOI21_kpart)	C++20	10 / 100	2095 ms	468 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long 
vector<bool>dp(50002);

void deep(int sum, vector<int>&v, int l, int r, vector<vector<bool>>& dp1){
    if(sum%2!=1){
        
        dp.assign(sum/2 +3, false);
        dp[0]=true;
        for(int i=l; i<=r; i++){
            if(dp[sum/2])break;
            for(int j=sum/2; j>=0; j--){
                if(j-v[i]>=0 && dp[j-v[i]])dp[j]=true;
            }
        }dp1[l][r]=dp[sum/2];
    }
}
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int t;
    cin>>t;
    for(int _=0; _<t; _++){
        int n;
        cin>>n;
        vector<int>a(n+2), sum(n+2);
        vector<vector<bool>>dp1(n+1, vector<bool>(n+1));
        for(int j=1; j<=n; j++){
            cin>>a[j];
            sum[j]=sum[j-1]+a[j];
            
        }for(int i=1; i<=n; i++){
            for(int j=i; j<=n; j++){
                deep(sum[j]-sum[j-i], a, j-i+1, j, dp1);
            }
        }
        vector<bool>check(n+1);
        for(int i=2; i<=n; i++){
            if(!check[i]){
            bool c=true;
            for(int j=i; j<=n; j++){
                if( !dp1[j-i+1][j]){
                    c=false;
                    break;
                }
            }if(c){
                for(int j=i; j<=n; j+=i){
                    check[j]=true;
                }
            }
            }
        }
        
        vector<int>q;
        for(int i=2; i<=n; i++){
            if(check[i])q.push_back(i);
        }cout<<q.size()<<" ";
        for(auto e: q)cout<<e<<" ";
        cout<<endl;
    }
    return 0;
}

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