oj.uz

Submission #794199

# Submission time Handle Problem Language Result Execution time Memory
794199 2023-07-26T10:34:37 Z Chal1shkan Kpart (eJOI21_kpart) C++14
100 / 100
 374 ms 98080 KB 
//Bismillahir-Rahmanir-Rahim

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

# include <bits/stdc++.h>
# define TIME (clock() * 1.0 / CLOCKS_PER_SEC)

# define pb push_back
# define ff first
# define ss second
# define nl "\n"
# define sz(x) ((int)(x).size())
# define all(x) (x).begin(), (x).end()
# define deb(x) cerr << #x  << " = " << x << endl; 
# define pll pair <ll, ll>
# define pii pair <int, int>
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
const ll maxn = 1e5 + 7;
const ll inf = 2e18 + 0;
const ll mod = 1e9 + 7;
const ll dx[] = {-1, 1, 0, 0};
const ll dy[] = {0, 0, -1, 1};

using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

short n;
int a[1003];
short dp[1003][50003];
int pref[1003];
bitset <1003> ans;

void ma1n (/* SABR */)
{
    cin >> n;
    for (short i = 1; i <= n; ++i)
    {
        cin >> a[i];
    	pref[i] = pref[i - 1] + a[i]; 
	}
	for (short i = 1; i <= n; ++i)
	{
		for (int j = 0; j <= pref[n] / 2; ++j)
		{
			dp[i][j] = 0;
		}
	}
	ans.reset();
	for (short k = 2; k <= n; ++k) ans[k] = 1;
	for (short i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= pref[n] / 2; ++j)
		{
			dp[i][j] = dp[i - 1][j];
			if (j > a[i])
			{
				dp[i][j] = max(dp[i][j], dp[i - 1][j - a[i]]);
			}
			else if (j == a[i])
			{
				dp[i][j] = i;
			}
		}
		for (short k = 2; k <= i; ++k)
		{	
			int sum = pref[i] - pref[i - k];
			if (sum & 1)
			{
				ans[k] = 0;
			}
			if (dp[i][sum / 2] < i - k + 1)
			{
				ans[k] = 0; 
			}
		}
	}
    cout << ans.count() << ' ';
    for(short i = ans._Find_first(); i <= n; i = ans._Find_next(i))
    {
    	cout << i << ' ';
	}
	cout << nl;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//  freopen("file.in", "r", stdin);
//  freopen("file.out", "w", stdout);
    int ttt = 1;
    cin >> ttt;
    for (int test = 1; test <= ttt; ++test)
    {
//      cout << "Case " << test << ":" << '\n';
        ma1n();
    }
    return 0;
}

// 998batrr | BbIWEJI 3A TObOU!!!
// tourist  | BbIWEJI 3A TObOU!!!

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1108 KB Output is correct
2 Correct 4 ms 2260 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 7820 KB Output is correct
2 Correct 47 ms 16692 KB Output is correct
3 Correct 68 ms 21116 KB Output is correct
4 Correct 120 ms 34624 KB Output is correct
5 Correct 276 ms 83016 KB Output is correct
6 Correct 374 ms 96640 KB Output is correct
7 Correct 341 ms 98080 KB Output is correct