oj.uz

Submission #851779

# Submission time Handle Problem Language Result Execution time Memory
851779 2023-09-20T15:12:28 Z rahidilbayramli Kpart (eJOI21_kpart) C++17
0 / 100
 2000 ms 348 KB 
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define vl vector<ll>
#define vi vector<int>
#define all(v) v.begin(), v.end()
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define f first
#define s second
using namespace std;
int main()
{
    ll t = 1;
    cin >> t;
    while(t--){
        ll n, i, j, k, x, sum, p, sz, sum2, sum3 = 0;
        cin >> n;
        ll w[n+1];
        vl v;
        for(i = 1; i <= n; i++){
            cin >> w[i];
            sum3 += w[i];
        }
        bool flag, flag2;
        vl ans;
        for(k = 2; k <= n - 1; k++){
            flag = false;
            for(j = 1; j <= n - k + 1; j++){
                sum = 0;
                vl v;
                for(i = j; i <= j + k - 1; i++){
                    sum += w[i];
                    v.pb(w[i]);
                }
                if(sum % 2){
                    flag = true;
                    break;
                }
                else{
                    sz = v.size();
                    flag2 = true;
                    for(i = 0; i < 1 << sz; i++){
                        sum2 = 0;
                        for(p = 0; p < sz; p++){
                            if((i >> p) & 1)
                                sum2 += v[p];
                        }
                        if(sum2 == sum / 2)
                            flag2 = false;
                    }
                    if(flag2)
                    {
                        flag = true;
                        break;
                    }
                }
            }
            if(!flag)
                ans.pb(k);
        }
        if(sum3 % 2 == 0){
            sum3 /= 2;
            bool possible[100005];
            possible[0] = true;
            for(i = 1; i <= n; i++)
            {
                for(x = sum3 - w[i]; x >= 0; x--)
                    possible[x + w[i]] |= possible[x];
            }
            if(possible[sum3])
                ans.pb(n);
        }
        cout << ans.size() << ' ';
        for(ll&h : ans)
            cout << h << ' ';
        cout << '\n';
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2054 ms 348 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2060 ms 348 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2029 ms 344 KB Time limit exceeded
2 Halted 0 ms 0 KB -