oj.uz

Submission #402263

# Submission time Handle Problem Language Result Execution time Memory
402263 2021-05-11T13:23:54 Z yoavL Bali Sculptures (APIO15_sculpture) C++14
0 / 100
 1000 ms 4632 KB 
#include <iostream>
#include <vector>
#include <algorithm>

#define upmax(a, b) a = max(a, b);
#define upmin(a, b) a = min(a, b);
#define pr(x) cout << x << endl;

using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;

const ll inf = 1e18;
const ll maxn = 502;
const ll maxg = 20;
ll n, a, b;
vll arr;
ll ans;
vll s;

void brute(vll& div, ll ind)
{
	if (ind == n) {
		if (div.size() < a-1 || div.size() > b-1) return;
		ll res = 0;
		ll cursum = 0;
		ll p = 0;
		for (ll i = 0; i < n; i++) {
			cursum += arr[i];
			if (p < div.size() && div[p] == i) {
				res |= cursum;
				p++;
				cursum = 0;
			}
		}
		res |= cursum;
		upmin(ans, res);
		return;
	}

	div.push_back(ind);
	if(ind < n-1) brute(div, ind + 1);
	div.pop_back();
	brute(div, ind + 1);
}


ll sum(ll l, ll r)
{
	ll res = s[r];
	if (l) res -= s[l - 1];
	return res;
}


ll calc_dp()
{
	
	/*
	dp[i][j][k] = is it possible to use first i vals to form j groups with OR-SUM equals k.
	*/

	vvvll dp(n+1, vvll(maxg + 1, vll(maxn, false)));

	dp[0][0][0] = true;

	for (ll i = 1; i <= n; i++) {
		for (ll j = 1; j <= maxg; j++) {
			for (ll k = 0; k < maxn; k++) {
				for (ll m = 0; m < i; m++) {
					if ((sum(m, i-1) | k) != k) continue;
					for (ll t = 0; t < maxn; t++) {
						if ((t | k) != k) continue;
						dp[i][j][k] |= dp[m][j - 1][t];
					}
				}
			}
		}
	}

	ll res = inf;
	for (ll j = a; j <= b; j++) {
		for (ll k = 0; k < maxn; k++) {
			if (dp[n][j][k]) upmin(res, k);
		}
	}
	return res;
}

int main()
{
	cin >> n >> a >> b;
	arr.resize(n);
	for (ll i = 0; i < n; i++) cin >> arr[i];
	s.resize(n);
	s[0] = arr[0];
	for (ll i = 1; i < n; i++) s[i] = arr[i] + s[i - 1];
	ans = inf;
	//vll div;
	//brute(div, 0);
	//pr(ans);
	ans = calc_dp();
	pr(ans);
}

/*

6 1 3 
8 1 2 1 5 4


*/

Compilation message

sculpture.cpp: In function 'void brute(vll&, ll)':
sculpture.cpp:26:18: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   26 |   if (div.size() < a-1 || div.size() > b-1) return;
      |       ~~~~~~~~~~~^~~~~
sculpture.cpp:26:38: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   26 |   if (div.size() < a-1 || div.size() > b-1) return;
      |                           ~~~~~~~~~~~^~~~~
sculpture.cpp:32:10: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |    if (p < div.size() && div[p] == i) {
      |        ~~^~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 844 KB Output is correct
2 Correct 90 ms 1100 KB Output is correct
3 Correct 8 ms 420 KB Output is correct
4 Correct 28 ms 880 KB Output is correct
5 Correct 84 ms 1280 KB Output is correct
6 Correct 206 ms 1708 KB Output is correct
7 Correct 187 ms 1856 KB Output is correct
8 Correct 332 ms 2124 KB Output is correct
9 Correct 263 ms 2120 KB Output is correct
10 Correct 228 ms 2124 KB Output is correct
11 Correct 224 ms 2124 KB Output is correct
12 Correct 326 ms 2124 KB Output is correct
13 Correct 313 ms 2124 KB Output is correct
14 Correct 78 ms 944 KB Output is correct
15 Correct 91 ms 944 KB Output is correct
16 Correct 70 ms 844 KB Output is correct
17 Correct 23 ms 880 KB Output is correct
18 Correct 82 ms 1228 KB Output is correct
19 Correct 169 ms 1692 KB Output is correct
20 Correct 187 ms 1876 KB Output is correct
21 Correct 267 ms 2124 KB Output is correct
22 Correct 214 ms 2084 KB Output is correct
23 Correct 226 ms 2124 KB Output is correct
24 Correct 230 ms 2124 KB Output is correct
25 Correct 345 ms 2124 KB Output is correct
26 Correct 303 ms 2124 KB Output is correct
27 Incorrect 1 ms 844 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 844 KB Output is correct
2 Correct 90 ms 1100 KB Output is correct
3 Correct 9 ms 548 KB Output is correct
4 Correct 27 ms 844 KB Output is correct
5 Correct 85 ms 1188 KB Output is correct
6 Correct 205 ms 1692 KB Output is correct
7 Correct 190 ms 1868 KB Output is correct
8 Correct 322 ms 2120 KB Output is correct
9 Correct 242 ms 2124 KB Output is correct
10 Correct 224 ms 2124 KB Output is correct
11 Correct 226 ms 2124 KB Output is correct
12 Correct 307 ms 2116 KB Output is correct
13 Correct 325 ms 2124 KB Output is correct
14 Correct 78 ms 844 KB Output is correct
15 Correct 89 ms 940 KB Output is correct
16 Correct 72 ms 964 KB Output is correct
17 Correct 23 ms 804 KB Output is correct
18 Correct 83 ms 1272 KB Output is correct
19 Correct 167 ms 1612 KB Output is correct
20 Correct 193 ms 1860 KB Output is correct
21 Correct 269 ms 2124 KB Output is correct
22 Correct 239 ms 2124 KB Output is correct
23 Correct 227 ms 2104 KB Output is correct
24 Correct 226 ms 2124 KB Output is correct
25 Correct 339 ms 2124 KB Output is correct
26 Correct 304 ms 2124 KB Output is correct
27 Correct 307 ms 2244 KB Output is correct
28 Correct 364 ms 2524 KB Output is correct
29 Correct 704 ms 3652 KB Output is correct
30 Correct 943 ms 3936 KB Output is correct
31 Correct 949 ms 4608 KB Output is correct
32 Execution timed out 1020 ms 4612 KB Time limit exceeded
33 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 844 KB Output is correct
2 Correct 90 ms 1112 KB Output is correct
3 Correct 8 ms 460 KB Output is correct
4 Correct 29 ms 800 KB Output is correct
5 Correct 85 ms 1228 KB Output is correct
6 Correct 206 ms 1696 KB Output is correct
7 Correct 190 ms 1872 KB Output is correct
8 Correct 344 ms 2116 KB Output is correct
9 Correct 241 ms 2124 KB Output is correct
10 Correct 225 ms 2124 KB Output is correct
11 Correct 253 ms 2008 KB Output is correct
12 Correct 310 ms 2116 KB Output is correct
13 Correct 319 ms 2124 KB Output is correct
14 Correct 298 ms 2208 KB Output is correct
15 Correct 365 ms 2584 KB Output is correct
16 Correct 716 ms 3616 KB Output is correct
17 Correct 954 ms 3944 KB Output is correct
18 Correct 953 ms 4624 KB Output is correct
19 Execution timed out 1047 ms 4632 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 844 KB Output is correct
2 Correct 100 ms 1112 KB Output is correct
3 Correct 8 ms 588 KB Output is correct
4 Correct 28 ms 884 KB Output is correct
5 Correct 84 ms 1228 KB Output is correct
6 Correct 204 ms 1696 KB Output is correct
7 Correct 186 ms 1868 KB Output is correct
8 Correct 321 ms 2124 KB Output is correct
9 Correct 246 ms 2124 KB Output is correct
10 Correct 228 ms 2124 KB Output is correct
11 Correct 227 ms 2124 KB Output is correct
12 Correct 313 ms 2124 KB Output is correct
13 Correct 317 ms 2124 KB Output is correct
14 Correct 62 ms 844 KB Output is correct
15 Correct 88 ms 844 KB Output is correct
16 Correct 70 ms 844 KB Output is correct
17 Correct 23 ms 988 KB Output is correct
18 Correct 85 ms 1288 KB Output is correct
19 Correct 211 ms 1612 KB Output is correct
20 Correct 188 ms 1860 KB Output is correct
21 Correct 271 ms 2124 KB Output is correct
22 Correct 232 ms 2124 KB Output is correct
23 Correct 225 ms 2124 KB Output is correct
24 Correct 231 ms 2124 KB Output is correct
25 Correct 323 ms 2124 KB Output is correct
26 Correct 309 ms 2124 KB Output is correct
27 Incorrect 2 ms 844 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 844 KB Output is correct
2 Correct 91 ms 1108 KB Output is correct
3 Correct 8 ms 460 KB Output is correct
4 Correct 27 ms 844 KB Output is correct
5 Correct 86 ms 1228 KB Output is correct
6 Correct 206 ms 1700 KB Output is correct
7 Correct 189 ms 1828 KB Output is correct
8 Correct 324 ms 2124 KB Output is correct
9 Correct 242 ms 2124 KB Output is correct
10 Correct 222 ms 2124 KB Output is correct
11 Correct 228 ms 2124 KB Output is correct
12 Correct 312 ms 2124 KB Output is correct
13 Correct 314 ms 2124 KB Output is correct
14 Incorrect 1 ms 844 KB Output isn't correct
15 Halted 0 ms 0 KB -