제출 #1280688

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1280688		baktrr	Kpart (eJOI21_kpart)	C++20	10 / 100	2095 ms	572 KiB

Main

/**
  III     U   U  N   N  DDDD   EEEEE  RRRR   SSSS  TTTTT  AAAAA  N   N  DDDD      I  TTTTT     N   N   OOO   W   W
   I      U   U  NN  N  D   D  E      R   R  S       T    A   A  NN  N  D   D     I    T       NN  N  O   O  W   W
   I      U   U  N N N  D   D  EEEE   RRRR   SSSS    T    AAAAA  N N N  D   D     I    T       N N N  O   O  W W W
   I      U   U  N  NN  D   D  E      R  R      S    T    A   A  N  NN  D   D     I    T       N  NN  O   O  WW WW
  III     UUUUU  N   N  DDDD   EEEEE  R   R  SSSS    T    A   A  N   N  DDDD      I    T       N   N   OOO   W   W
**/

//18.09.25
#include <bits/stdc++.h>

#pragma optimize("g", on)
#pragma GCC optimize ("inline")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("03")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,avx2,mmx,fma,avx,tune=native")

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
using namespace std;
// using namespace __gnu_pbds;
 
#define ent '\n'
#define F first
#define S second
#define in insert
#define no "NO\n"
#define yes "YES\n"
#define pb push_back
#define sz(w) w.size()
#define int long long
#define pii pair <int, int>
#define all(w) w.begin(), w.end()
#define rall(w) w.rbegin(), w.rend()
#define BakTR ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
 
const int MOD = 998244353, N = 2e5 + 7 , inf = 1e9 + 7, INF = 2e18, LOG = 18 , mod = 1e9 + 7 ;
 
// template <typename T>
// using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

bool ch(deque <int> &v , int m) {
    int dp[m + 1] = {} ;
    dp[0] = 1 ;
    for(int i = 0 ; i < sz(v) ; i++) {
        for(int j = m ; j >= v[i] ; j--) {
            if(dp[j - v[i]] > 0) {
                dp[j] = 1 ;
            }
        }
    }
    return dp[m] ;
}


void accepted() {
    int n ;
    cin >> n ;
    int a[n + 1] , p[n + 2] = {} ;
    for(int i = 1 ; i <= n ; i++) {
        cin >> a[i] ;
        p[i] = p[i -1] + a[i] ;
    }
    vector <int> ans;
    for(int len = 1; len <= n; len++) {
        bool ok = 1 ;
        deque <int> d ;
        for(int i = 1 ; i <= len ; i++) d.pb(a[i]) ;
        for(int r = len ; r <= n ; r++) {
            int l = r - len + 1 ;
            if((p[r] - p[l - 1]) % 2) {
                ok = 0 ;
                break;
            }
            if(!ch(d , (p[r] - p[l - 1]) / 2)) {
                ok = 0 ;
                break ;
            }
            if(r + 1 <= n) {
                d.pop_front();
                d.pb(a[r + 1]);
            }
        }
        if(ok) {
            ans.pb(len);
        }
    }
    cout << sz(ans) << ' ' ;
    for(int to : ans) {
        cout << to << ' ' ;
    }
}

signed main() {
    BakTR
 
    //PLS NeverGiveUp
 
    // freopen("trains.in", "r", stdin) ;
    // freopen("trains.out", "w", stdout) ;
 
    int T = 1 ;
    cin >> T ;
    while (T--) {
        accepted();
        cout << ent;
    }
}
/**
baktr


**/

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