제출 #1347963

#제출 시각아이디문제언어결과실행 시간메모리
1347963almaarmudKpart (eJOI21_kpart)C++20
30 / 100
2094 ms456 KiB
/*
██████╗  █████╗ ███████╗██╗  ██╗██╗██████╗
██╔══██╗██╔══██╗██╔════╝██║  ██║██║██╔══██╗
██████╔╝███████║███████╗███████║██║██║   ██║
██╔══██╗██╔══██║╚════██║██╔══██║██║██║   ██║
██║  ██║██║  ██║███████║██║  ██║██║██████╔╝
╚═╝  ╚═╝╚═╝  ╚═╝╚══════╝╚═╝  ╚═╝╚═╝╚═════╝
*/
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ll long long
#define ull unsigned long long
#define ld long double
#define str string
#define ch char
#define db double
#define pb push_back
#define ff first
#define ss second
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define YES cout<<"YES\n";
#define NO cout<<"NO\n";
#define Bob cout<<"Bob\n";
#define Alice cout<<"Alice\n";
#define ordered_set tree<pair<ll, ll>, null_type,less<pair<ll,ll>>,rb_tree_tag,tree_order_statistics_node_update>
const ll MOD=1e9+7;
const ll INF = 10000000000;
bool dp[50001];
bool duzdu(vector<ll>subarray,ll start,ll end){
  ll sum = 0;
  for(ll i = start;i<end;i++)sum+=subarray[i];
  if(sum%2!=0)return false;
  for(ll i = 0;i<=sum/2;i++){
    dp[i]=false;
  }
  dp[0]=true;
  ll mx=0;
  for(ll i = start;i<end;i++){
    ll alma = subarray[i];
    for(ll j = min(sum/2,mx+alma);j>=alma;j--){
      if(dp[j-alma]){
        dp[j]=true;
      }
    }
    mx = min(sum/2,mx+alma);
    if(dp[sum/2])return true;
  }
  return dp[sum/2];
}
void solve(){
    ll n;
    cin>>n;
    vector<ll>v(n);
    for(int i = 0;i<n;i++){
      cin>>v[i];
    }
    vector<ll>ans;
    for(ll k = 1;k<=n;k++){
      bool ok = true;
      for(ll i = 0;i<=n-k;i++){
        if(!duzdu(v,i,i+k)){
          ok=false;
          break;
        }
      }
      if(ok){
        ans.pb(k);
      }
    }
    cout<<ans.size()<<" ";
    for(auto p : ans)cout<<p<<" ";
    cout<<"\n";
}
signed main(){
    ll t=1;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...