Submission #1128189

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128189		asdfghjk	Kpart (eJOI21_kpart)	C++20	10 / 100	2095 ms	6192 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define pb push_back
#define all(x) x.begin(), x.end()
#define con continue
#define F first
#define S second

using namespace std;
using namespace __gnu_pbds;

template<typename T> using indexed_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pii;


const ll N = 1e5 + 5;
const ll NN =   1e6 + 1e5;
const ll INF = 1e18;
const ll inf = 1e9;
const ll MOD = 1e9 + 7;
int a[1005],pre[1005],cnt[1005];
int dp[N];
set <int> g[N];
void solve(){
    int n;cin >> n;
    for(int i = 1;i <= n;i++){
        cin >> a[i];
        g[i].clear();
        pre[i] =pre[i - 1] + a[i];
    }
    int x = 100000;
    dp[0] = 1;
    for(int i = 2;i <= n;i++){
        for(int j = 1;j <= x;j++){
            dp[j] = 0;
        }
        dp[a[i]] = 1;
        for(int j = i - 1;j > 0;j--){
            for(int d =x;d >= a[j];d--){
                dp[d] = max(dp[d],dp[d - a[j]]);
            }
            int sum = (pre[i] - pre[j - 1]);
            if(sum % 2 == 0 && dp[(sum / 2)] == 1){
                g[i].insert((i -j + 1));
            }
        }
    }
    for(int i = 0;i <= n;i++)cnt[i] = 0;
    for(int i = 1;i <= n;i++){
        for(int to : g[i]){
            cnt[to]++;
        }
    }
    vector <int> ans;
    ans.clear();
    for(int i = 2;i <= n;i++){
        if(cnt[i] == n - i + 1){
            ans.pb(i);
        }
    }
    cout << ans.size() << ' ';
    for(int to : ans){
        cout << to << ' ';
    }
    cout << '\n';
}

main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    cout.tie(0);
    ll abd = 1;
    cin >>abd;
//    freopen("promote.in","r",stdin);
//    freopen("promote.out","w",stdout);
    for(ll i = 1;i <= abd;i++){

        solve();
    }
}

Compilation message (stderr)

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

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