Submission #1266828

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266828		syanvu	Kpart (eJOI21_kpart)	C++20	0 / 100	738 ms	200848 KiB

Main

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp> 
// #include <ext/pb_ds/tree_policy.hpp>

#define SS ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
#pragma optimize("g", on)
#pragma GCC optimize("03")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,avx2,mmx,fma,avx,tune=native")
#define int long long
#define all(x) x.begin(),x.end()
#define F first
#define S second


using namespace std;
// using namespace __gnu_pbds; 
// #define ordered_set tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>

const int LG = 21,N = 1e3 + 1,MX = 1e5 + 1,inf = 1e18,MOD = 998244353;
const double eps = 1e-9;
int T=1;

int dp[N][MX];

void solve() {
    int n;
    cin>>n;
    int a[n+1];
    int pref[n+1]={};
    for(int i=1;i<=n;i++){
        cin>>a[i];
        pref[i]=pref[i-1]+a[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<MX;j++) dp[i][j]=0;
    }
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int sum=0;sum<MX;sum++){
            dp[i][sum] |= dp[i-1][sum];
            if(sum-a[i]>=0) dp[i][sum] |= dp[i-1][sum-a[i]];
        }
    }
    vector<int> res;
    for(int k=2;k<=n;k++){
        bool ok=0;
        for(int l=1;l+k-1<=n;l++){
            int r=l+k-1;
            int d=pref[l-1];
            int g=pref[r]-pref[l-1];
            if((g%2) || !dp[r][g/2+d]){
                ok=1;
                // cout<<g<<' '<<r<<'\n';
                break;
            }
        }
        if(!ok) res.push_back(k);
    }
    cout<<res.size()<<' ';
    for(int k:res) cout<<k<<' ';
    cout<<'\n';
    return;
}
signed main() {
    //   freopen("deleg.in","r",stdin);    
    // freopen("deleg.out","w",stdout);
    SS
    int t = 1;
    if (T) {
        cin >> t;
    }
    while (t--) {
        solve();
    }
}
/*
{x,y,z} {x,y,z}
 sum/2   sum/2

sz - ok

 */

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