oj.uz

Submission #556130

# Submission time Handle Problem Language Result Execution time Memory
556130 2022-05-02T12:30:02 Z Skurrl Kpart (eJOI21_kpart) C++17
10 / 100
 2000 ms 432 KB 
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define N 100005
#define MOD 1000000007
#define endl '\n'
#define all(x) x.begin(), x.end()

typedef long long int ll;

const ll inf = 1e17;

void solve()
{
    int n; cin >> n;
    vector<int> arr(n + 1);

    for(int i = 1; i <= n; ++i) cin >> arr[i];

    vector<int> ks;

    for (int k = 1; k <= n; ++k)
    {
        bool ok = true;
        for (int i = 1; i + k - 1 <= n; ++i)
        {
            int sum = 0;

            for(int j = i; j <= i + k - 1; ++j) 
                sum += arr[j];

            if(!(sum & 1))
            {
                vector<bool> part(sum / 2 + 1);

                for (int j = i; j <= i + k - 1; ++j)
                {
                    for(int l = sum / 2; l >= 0; --l)
                    {
                        if((l - arr[j] >= 0) and part[l - arr[j]] == 1 or l == arr[j]) part[l] = true;
                    }
                }

                ok &= part[sum / 2];
            }

            ok &= (sum % 2 == 0);
        }

        if(ok) ks.pb(k);
    }

    cout << ks.size() << " ";
    for(auto i : ks) cout << i << " ";

    cout << endl;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ll t; cin >> t;
    while(t--)
        solve();
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:41:46: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   41 |                         if((l - arr[j] >= 0) and part[l - arr[j]] == 1 or l == arr[j]) part[l] = true;
      |                            ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 212 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 979 ms 308 KB Output is correct
2 Execution timed out 2089 ms 316 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 2091 ms 432 KB Time limit exceeded
2 Halted 0 ms 0 KB -