Submission #549140

#	Time	Username	Problem	Language	Result	Execution time	Memory
549140		spike1236	Kpart (eJOI21_kpart)	C++14	30 / 100	2079 ms	480 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define veci vector <int>
#define ll long long
#define sz(_v) (int)_v.size()

const int MAXN = 1e5 + 10;
///const int MOD = 1e9 + 7;
unsigned int dp[MAXN];
int S, n;
int a[1010];
int pref[1010];

void del(int x) {
    for(int i = x; i <= S; ++i) dp[i] -= dp[i - x];
    ///if(dp[i] < 0) dp[i] += MOD;
}

void add(int x) {
    for(int i = S; i >= x; --i) dp[i] += dp[i - x];
    ///if(dp[i] >= MOD) dp[i] -= MOD;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    dp[0] = 1;
    for(int cs = 1; cs <= t; ++cs) {
        cin >> n;
        int gc = 0;
        for(int i = 1; i <= n; ++i) {
            cin >> a[i];
            gc = __gcd(gc, a[i]);
        }
        for(int i = 1; i <= n; ++i) {
            a[i] /= gc;
            pref[i] = pref[i - 1] + a[i];
        }
        veci ans;
        for(int len = 2; len <= n; ++len) {
            char can = 1;
            for(int i = 1; i + len - 1 <= n; ++i) {
                if((pref[i + len - 1] - pref[i - 1]) % 2 != 0) {
                    can = 0;
                    break;
                }
            }
            if(!can) continue;
            multiset <int> st;
            for(int i = 1; i <= len; ++i) st.insert(a[i]);
            if(*st.rbegin() > pref[len] / 2) continue;
            for(int i = len + 1; i <= n; ++i) {
                st.erase(st.find(a[i - len]));
                st.insert(a[i]);
                if(*st.rbegin() > (pref[i] - pref[i - len]) / 2 || *st.begin() > (pref[i] - pref[i - len]) / 4) {
                    can = 0;
                    break;
                }
            }
            if(!can) continue;
            S = pref[len];
            for(int l = 1; l <= len; ++l) add(a[l]);
            if(dp[S >> 1] == 0) {
                for(int i = 1; i <= S; ++i) dp[i] = 0;
                continue;
            }
            for(int r = len + 1; r <= n; ++r) {
                del(a[r - len]);
                S -= a[r - len];
                S += a[r];
                add(a[r]);
                if(dp[S >> 1] == 0) {
                    for(int i = 1; i <= S; ++i) dp[i] = 0;
                    can = 0;
                    break;
                }
            }
            if(can) {
                for(int i = 1; i <= S; ++i) dp[i] = 0;
                ans.pb(len);
            }
        }
        cout << sz(ans) << ' ';
        for(auto it : ans) cout << it << ' ';
        cout << '\n';
    }
    return 0;
}

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