oj.uz

Submission #626180

# Submission time Handle Problem Language Result Execution time Memory
626180 2022-08-11T09:31:41 Z Blagoj Kpart (eJOI21_kpart) C++14
10 / 100
 2000 ms 324 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
int a[1001], total = 0;
bool solve(int l, int r)
{
    bool dp[total / 2 + 1];
    memset(dp, false, total / 2 + 1);
    dp[0] = true;
    int mx = 0;
    for (int i = l; i <= r; i++)
    {
        for (int j = mx; j >= 0; j--)
        {
            if (dp[j] && (j + a[i]) * 2 <= total)
            {
                if ((j + a[i]) * 2 == total)
                {
                    return true;
                }
                dp[j + a[i]] = true;
                mx = max(mx, j + a[i]);
            }
        }
    }
    return false;
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int t;
    cin >> t;
    int n;
    bool possible = true;
    while (t--)
    {
        cin >> n;
        for (int i = 0; i < n; i++)
        {
            cin >> a[i];
        }
        vector<int> v;
        for (int sz = 2; sz <= n; sz++)
        {
            possible = true;
            total = 0;
            for (int i = 0; i < sz; i++)
            {
                total += a[i];
            }
            for (int i = 0; i + sz <= n; i++)
            {
                if (i > 0)
                {
                    total -= a[i - 1];
                    total += a[i + sz - 1];
                }
                if (!solve(i, i + sz - 1))
                {
                    possible = false;
                    break;
                }
            }
            if (possible)
            {
                v.push_back(sz);
            }
        }
        cout << v.size() << " ";
        for (auto x : v)
        {
            cout << x << " ";
        }
        cout << "\n";
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 316 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 324 KB Output is correct
2 Execution timed out 2089 ms 312 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

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