Submission #1221812

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221812		Robert_junior	Kpart (eJOI21_kpart)	C++20	100 / 100	578 ms	928 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()
#define ins insert
#define pb push_back
#define F first
#define S second
const int N = 1e6+4, M = 5e5 + 7;
const int mod = 1e9 + 7;
int a[N], ok[N];
int dp[N], pf[N];
void solve(){
    int n;
    cin>>n;
    for(int i = 1; i <= n; i++){
        cin>>a[i];
        pf[i] = pf[i - 1] + a[i];
        ok[i] = 1;
    }
    for(int i = 1; i <= 50000; i++){
        dp[i] = 0;
    }
    for(int i = 1; i <= n; i++){
        for(int j = 50000; j >= a[i]; j--){
            dp[j] = max(dp[j], dp[j - a[i]]);
        }
        if(a[i] <= 50000){
            dp[a[i]] = i;
        }
        for(int j = i - 1; j >= 1; j--){
            int sum = pf[i] - pf[j - 1];
            //cout<<j<<' '<<i<<' '<<sum<<' '<<dp[sum / 2]<<'\n';
            if(sum % 2 == 0 && dp[sum / 2] >= j) continue;
            ok[(i - j + 1)] = 0;
        }
    }
    vector<int>res;
    for(int i = 2; i <= n; i++) if(ok[i]) res.pb(i);
    cout<<res.size()<<' ';
    for(auto it : res) cout<<it<<' ';
    cout<<'\n';
}
main(){
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr); 
    int t = 1;
    cin>>t; 
    for(int i = 1; i <= t; i++){
        //cout<<"Case "<<i<<": ";
        solve();
    }
}

Compilation message (stderr)

Main.cpp:44:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   44 | main(){
      | ^~~~

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