Submission #1236616

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236616		minhpk	Kpart (eJOI21_kpart)	C++20	100 / 100	827 ms	25568 KiB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;
int z[1000005];
int dp[1000005];
int prefix[1000005];
int cnt[1000005];
vector <int> q[1000005];

void solve(){
    int a;
    cin >> a;
    for (int i=1;i<=a;i++){
         cin >> z[i];
         prefix[i]=prefix[i-1]+z[i];
    }
    int n=prefix[a];
    for (int i=1;i<=prefix[a];i++){
         dp[i]=0;
         cnt[i]=1;
    }
    for (int i=1;i<=a;i++){
         for (int s=n;s>=z[i];s--){
              dp[s]=max(dp[s],dp[s-z[i]]);
         }
         dp[z[i]]=max(dp[z[i]],i);
         for (int j=1;j<=a;j++){
              int l=i-j+1;
              if (l<=0){
                 break;
              }
              int sum=prefix[i]-prefix[l-1];
              if (sum%2==1){
                  cnt[j]=0;
              }else{
                  int p=sum/2;
                  if (dp[p]>=dp[sum]){
                      cnt[j]*=1;
                  }else{
                      cnt[j]=0;
                  }
              }
         }
    }
    vector <int> v;
    for (int i=1;i<=a;i++){
         if (cnt[i]){
             v.push_back(i);
         }
    }
    cout << v.size() << " ";
    for (auto p:v){
         cout << p << " ";
    }
    cout << "\n";
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--){
        solve();
    }
    return 0;
}

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