oj.uz

Submission #110022

# Submission time Handle Problem Language Result Execution time Memory
110022 2019-05-08T22:34:43 Z aminra Bali Sculptures (APIO15_sculpture) C++14
71 / 100
 10 ms 1792 KB 
//I forgot you...
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MOD = (int)1e9 + 7;
const int MAXN = 103;
const int base = 37;
const int infint = (int)1e9 + 3;
const ll inf = (ll)1e18;
ll n, A, B, dp[MAXN][MAXN], a[MAXN], part[MAXN];
ll dist[MAXN];
vector<ll> G[MAXN];
void calc()
{
	dp[0][0] = 1;
	for (int i = 0; i <= n - 1; i++)
		for (int j = 0; j <= i; j++)
			if(dp[i][j])
				for (auto u : G[i])
					dp[u][j + 1] = 1;
}
void calc2()
{
	dist[0] = 0;
	for (int i = 0; i <= n - 1; i++)
		for (auto u : G[i])
			dist[u] = min(dist[u], dist[i] + 1);
}
int main()
{
	ios::sync_with_stdio(false); 
	cin.tie(0); cout.tie(0);
	cin >> n >> A >> B;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= n; i++)
		part[i] = part[i - 1] + a[i];
	if(A == 1)
	{
		ll ans = 0;
		for (ll i = 50; i >= 0; i--)
		{
			ans += (1LL << i);
			for (int j = 0; j <= n; j++)
				G[j].clear();
			memset(dist, 63, sizeof dist);
			for (ll j = 0; j <= n; j++)
				for (ll k = j + 1; k <= n; k++)
					if(((part[k] - part[j]) & ans) == 0)
						G[j].push_back(k);
			calc2();
			bool mika = (dist[n] <= B);
			if(mika == 0)
				ans -= (1LL << i);
		}
		cout << (1LL << 51) - 1 - ans;
		return 0;
	}
	ll ans = 0;
	for (ll i = 50; i >= 0; i--)
	{
		ans += (1LL << i);
		for (int j = 0; j <= n; j++)
			G[j].clear();
		memset(dp, 0, sizeof dp);
		for (ll j = 0; j <= n; j++)
			for (ll k = j + 1; k <= n; k++)
				if(((part[k] - part[j]) & ans) == 0)
					G[j].push_back(k);
		calc();
		bool mika = 0;
		for (int X = A; X <= B; X++)
			if(dp[n][X])
				mika = 1;
		if(mika == 0)
			ans -= (1LL << i);
	}
	cout << (1LL << 51) - 1 - ans;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Correct 3 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 3 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 3 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 3 ms 512 KB Output is correct
22 Correct 3 ms 384 KB Output is correct
23 Correct 3 ms 384 KB Output is correct
24 Correct 3 ms 384 KB Output is correct
25 Correct 3 ms 384 KB Output is correct
26 Correct 2 ms 512 KB Output is correct
27 Correct 3 ms 384 KB Output is correct
28 Correct 3 ms 384 KB Output is correct
29 Correct 2 ms 384 KB Output is correct
30 Correct 2 ms 384 KB Output is correct
31 Correct 2 ms 384 KB Output is correct
32 Correct 2 ms 384 KB Output is correct
33 Correct 3 ms 384 KB Output is correct
34 Correct 2 ms 384 KB Output is correct
35 Correct 2 ms 384 KB Output is correct
36 Correct 2 ms 384 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 3 ms 384 KB Output is correct
19 Correct 3 ms 384 KB Output is correct
20 Correct 3 ms 384 KB Output is correct
21 Correct 2 ms 384 KB Output is correct
22 Correct 3 ms 512 KB Output is correct
23 Correct 3 ms 512 KB Output is correct
24 Correct 2 ms 384 KB Output is correct
25 Correct 3 ms 384 KB Output is correct
26 Correct 3 ms 384 KB Output is correct
27 Correct 3 ms 384 KB Output is correct
28 Correct 2 ms 384 KB Output is correct
29 Correct 3 ms 384 KB Output is correct
30 Correct 2 ms 384 KB Output is correct
31 Correct 2 ms 384 KB Output is correct
32 Correct 3 ms 384 KB Output is correct
33 Correct 3 ms 352 KB Output is correct
34 Correct 2 ms 384 KB Output is correct
35 Correct 3 ms 412 KB Output is correct
36 Correct 2 ms 384 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 3 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 3 ms 384 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 3 ms 384 KB Output is correct
21 Correct 2 ms 384 KB Output is correct
22 Correct 2 ms 384 KB Output is correct
23 Correct 2 ms 384 KB Output is correct
24 Correct 3 ms 384 KB Output is correct
25 Correct 3 ms 384 KB Output is correct
26 Correct 3 ms 384 KB Output is correct
27 Correct 4 ms 384 KB Output is correct
28 Correct 4 ms 512 KB Output is correct
29 Correct 4 ms 384 KB Output is correct
30 Correct 3 ms 384 KB Output is correct
31 Correct 4 ms 384 KB Output is correct
32 Correct 4 ms 384 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Correct 3 ms 384 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 3 ms 384 KB Output is correct
20 Correct 3 ms 512 KB Output is correct
21 Correct 3 ms 512 KB Output is correct
22 Correct 3 ms 356 KB Output is correct
23 Correct 2 ms 384 KB Output is correct
24 Correct 2 ms 384 KB Output is correct
25 Correct 2 ms 384 KB Output is correct
26 Correct 2 ms 512 KB Output is correct
27 Correct 2 ms 384 KB Output is correct
28 Correct 2 ms 384 KB Output is correct
29 Correct 3 ms 384 KB Output is correct
30 Correct 3 ms 384 KB Output is correct
31 Correct 2 ms 384 KB Output is correct
32 Correct 2 ms 384 KB Output is correct
33 Correct 2 ms 384 KB Output is correct
34 Correct 2 ms 384 KB Output is correct
35 Correct 2 ms 384 KB Output is correct
36 Correct 2 ms 384 KB Output is correct
37 Correct 2 ms 384 KB Output is correct
38 Correct 3 ms 384 KB Output is correct
39 Correct 3 ms 384 KB Output is correct
40 Correct 3 ms 384 KB Output is correct
41 Correct 2 ms 384 KB Output is correct
42 Correct 3 ms 384 KB Output is correct
43 Correct 2 ms 384 KB Output is correct
44 Correct 3 ms 384 KB Output is correct
45 Correct 3 ms 384 KB Output is correct
46 Correct 3 ms 384 KB Output is correct
47 Correct 3 ms 384 KB Output is correct
48 Correct 3 ms 384 KB Output is correct
49 Correct 3 ms 384 KB Output is correct
50 Correct 3 ms 512 KB Output is correct
51 Correct 3 ms 384 KB Output is correct
52 Correct 4 ms 384 KB Output is correct
53 Correct 4 ms 512 KB Output is correct
54 Correct 4 ms 384 KB Output is correct
55 Correct 4 ms 384 KB Output is correct
56 Correct 2 ms 384 KB Output is correct
57 Correct 3 ms 384 KB Output is correct
58 Correct 3 ms 384 KB Output is correct
59 Correct 3 ms 384 KB Output is correct
60 Correct 3 ms 384 KB Output is correct
61 Correct 3 ms 384 KB Output is correct
62 Correct 3 ms 384 KB Output is correct
63 Correct 3 ms 384 KB Output is correct
64 Correct 10 ms 512 KB Output is correct
65 Correct 5 ms 512 KB Output is correct
66 Correct 5 ms 384 KB Output is correct
67 Correct 5 ms 512 KB Output is correct
68 Correct 6 ms 512 KB Output is correct
69 Correct 7 ms 512 KB Output is correct
70 Correct 8 ms 512 KB Output is correct
71 Correct 7 ms 512 KB Output is correct
72 Correct 8 ms 512 KB Output is correct
73 Correct 8 ms 512 KB Output is correct
74 Correct 7 ms 512 KB Output is correct

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 2 ms 384 KB Output is correct
22 Correct 2 ms 384 KB Output is correct
23 Correct 2 ms 384 KB Output is correct
24 Correct 3 ms 384 KB Output is correct
25 Correct 3 ms 384 KB Output is correct
26 Correct 2 ms 384 KB Output is correct
27 Correct 4 ms 384 KB Output is correct
28 Correct 3 ms 384 KB Output is correct
29 Correct 3 ms 384 KB Output is correct
30 Correct 3 ms 384 KB Output is correct
31 Correct 3 ms 384 KB Output is correct
32 Correct 3 ms 384 KB Output is correct
33 Correct 2 ms 384 KB Output is correct
34 Correct 3 ms 384 KB Output is correct
35 Correct 2 ms 384 KB Output is correct
36 Correct 2 ms 384 KB Output is correct
37 Correct 2 ms 384 KB Output is correct
38 Correct 3 ms 384 KB Output is correct
39 Correct 3 ms 384 KB Output is correct
40 Correct 4 ms 384 KB Output is correct
41 Correct 3 ms 384 KB Output is correct
42 Correct 3 ms 384 KB Output is correct
43 Correct 3 ms 384 KB Output is correct
44 Correct 3 ms 384 KB Output is correct
45 Correct 3 ms 384 KB Output is correct
46 Correct 3 ms 384 KB Output is correct
47 Correct 3 ms 384 KB Output is correct
48 Correct 4 ms 384 KB Output is correct
49 Correct 3 ms 384 KB Output is correct
50 Correct 3 ms 384 KB Output is correct
51 Correct 4 ms 384 KB Output is correct
52 Runtime error 4 ms 1792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
53 Halted 0 ms 0 KB -