답안 #77304 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
77304	2018-09-25T03:19:21 Z	qkxwsm	Bali Sculptures (APIO15_sculpture)	C++17	25 / 100	1000 ms	764 KB

sculpture

/*
PROG: source
LANG: C++11
_____
.'     '.
/  0   0  \
|     ^     |
|  \     /  |
\  '---'  /
'._____.'
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

struct chash
{
	int operator()(int x) const
	{
		x ^= (x >> 20) ^ (x >> 12);
		return x ^ (x >> 7) ^ (x >> 4);
	}
	int operator()(long long x) const
	{
		return x ^ (x >> 32);
	}
};

template<typename T> using orderedset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename U> using hashtable = gp_hash_table<T, U, chash>;

template<class T>
void readi(T &x)
{
	T input = 0;
	bool negative = false;
	char c = ' ';
	while (c < '-')
	{
		c = getchar();
	}
	if (c == '-')
	{
		negative = true;
		c = getchar();
	}
	while (c >= '0')
	{
		input = input * 10 + (c - '0');
		c = getchar();
	}
	if (negative)
	{
		input = -input;
	}
	x = input;
}
template<class T>
void printi(T output)
{
	if (output == 0)
	{
		putchar('0');
		return;
	}
	if (output < 0)
	{
		putchar('-');
		output = -output;
	}
	int aout[20];
	int ilen = 0;
	while(output)
	{
		aout[ilen] = ((output % 10));
		output /= 10;
		ilen++;
	}
	for (int i = ilen - 1; i >= 0; i--)
	{
		putchar(aout[i] + '0');
	}
	return;
}
template<class T>
void ckmin(T &a, T b)
{
	a = min(a, b);
}
template<class T>
void ckmax(T &a, T b)
{
	a = max(a, b);
}
template<class T, class U>
T normalize(T x, U mod = 1000000007)
{
	return (((x % mod) + mod) % mod);
}
long long randomizell(long long mod)
{
	return ((1ll << 45) * rand() + (1ll << 30) * rand() + (1ll << 15) * rand() + rand()) % mod;
}
int randomize(int mod)
{
	return ((1ll << 15) * rand() + rand()) % mod;
}

#define y0 ___y0
#define y1 ___y1
#define MP make_pair
#define MT make_tuple
#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define debug(x) cerr << #x << " = " << x << endl;

const long double PI = 4.0 * atan(1.0);
const long double EPS = 1e-10;

#define MAGIC 347
#define SINF 10007
#define CO 1000007
#define INF 1000000007
#define BIG 1000000931
#define LARGE 1696969696967ll
#define GIANT 2564008813937411ll
#define LLINF 2696969696969696969ll
#define MAXN 113

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;

int N, L, R;
ll arr[MAXN], pref[MAXN];
bitset<MAXN> edge[MAXN], ok[MAXN];
ll ans = LLINF, best;

ll solve(int d)
{
	best = 0;
	for (int i = 0; i <= N; i++)
	{
		edge[i].set();
	}
	for (int i = 50; i >= 0; i--)
	{
		for (int j = 0; j <= N; j++) ok[j].reset();
		ok[0][0] = true;
		for (int j = 0; j < N; j++)
		{
			for (int k = j + 1; k <= N; k++)
			{
				if (!edge[j][k]) continue;
				ll rsum = pref[k] - pref[j];
				for (int m = 0; m <= R; m++)
				{
					if (!ok[j][m])
					{
						continue;
					}
					if (!(rsum & (1ll << i)))
					{
						ok[k][m + 1] = true;
					}
				}
			}
		}
		if (!ok[N][d])
		{
			best += (1ll << i);
		}
		else
		{
			for (int j = 0; j < N; j++)
			{
				for (int k = j + 1; k <= N; k++)
				{
					ll rsum = pref[k] - pref[j];
					if (rsum & (1ll << i))
					{
						edge[j][k] = false;
					}
				}
			}
		}
	}
	//delete an edge, ask if there's a path between 0 and v in exactly m moves
	return best;
}

int32_t main()
{
	ios_base::sync_with_stdio(0);
	srand(time(0));
	//	cout << fixed << setprecision(10);
	//	cerr << fixed << setprecision(10);
	if (fopen("input.in", "r"))
	{
		freopen ("input.in", "r", stdin);
		freopen ("output.out", "w", stdout);
	}
	cin >> N >> L >> R;
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
		pref[i + 1] = pref[i] + arr[i];
	}
	for (int i = L; i <= R; i++)
	{
		ckmin(ans, solve(i));
	}
	cout << ans << '\n';
	//	cerr << "time elapsed = " << (clock() / (CLOCKS_PER_SEC / 1000)) << " ms" << endl;
	return 0;
}

Compilation message

sculpture.cpp: In function 'int32_t main()':
sculpture.cpp:209:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen ("input.in", "r", stdin);
   ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:210:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen ("output.out", "w", stdout);
   ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	464 KB	Output is correct
3	Correct	2 ms	472 KB	Output is correct
4	Correct	2 ms	472 KB	Output is correct
5	Correct	2 ms	472 KB	Output is correct
6	Correct	6 ms	472 KB	Output is correct
7	Correct	3 ms	496 KB	Output is correct
8	Correct	3 ms	496 KB	Output is correct
9	Correct	2 ms	556 KB	Output is correct
10	Correct	2 ms	556 KB	Output is correct
11	Correct	3 ms	556 KB	Output is correct
12	Correct	2 ms	708 KB	Output is correct
13	Correct	10 ms	708 KB	Output is correct
14	Correct	2 ms	708 KB	Output is correct
15	Correct	2 ms	708 KB	Output is correct
16	Correct	2 ms	708 KB	Output is correct
17	Correct	2 ms	708 KB	Output is correct
18	Correct	2 ms	708 KB	Output is correct
19	Correct	3 ms	708 KB	Output is correct
20	Correct	2 ms	708 KB	Output is correct
21	Correct	3 ms	708 KB	Output is correct
22	Correct	3 ms	708 KB	Output is correct
23	Correct	3 ms	708 KB	Output is correct
24	Correct	2 ms	708 KB	Output is correct
25	Correct	4 ms	708 KB	Output is correct
26	Correct	5 ms	708 KB	Output is correct
27	Correct	2 ms	708 KB	Output is correct
28	Correct	2 ms	708 KB	Output is correct
29	Correct	3 ms	708 KB	Output is correct
30	Correct	2 ms	708 KB	Output is correct
31	Correct	3 ms	708 KB	Output is correct
32	Correct	2 ms	708 KB	Output is correct
33	Correct	5 ms	708 KB	Output is correct
34	Correct	10 ms	708 KB	Output is correct
35	Correct	2 ms	708 KB	Output is correct
36	Correct	16 ms	708 KB	Output is correct

Subtask #2
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	708 KB	Output is correct
2	Correct	2 ms	708 KB	Output is correct
3	Correct	2 ms	752 KB	Output is correct
4	Correct	2 ms	752 KB	Output is correct
5	Correct	2 ms	752 KB	Output is correct
6	Correct	5 ms	752 KB	Output is correct
7	Correct	3 ms	752 KB	Output is correct
8	Correct	2 ms	752 KB	Output is correct
9	Correct	2 ms	752 KB	Output is correct
10	Correct	3 ms	752 KB	Output is correct
11	Correct	2 ms	752 KB	Output is correct
12	Correct	3 ms	752 KB	Output is correct
13	Correct	10 ms	752 KB	Output is correct
14	Correct	2 ms	752 KB	Output is correct
15	Correct	2 ms	760 KB	Output is correct
16	Correct	2 ms	760 KB	Output is correct
17	Correct	2 ms	760 KB	Output is correct
18	Correct	2 ms	760 KB	Output is correct
19	Correct	2 ms	760 KB	Output is correct
20	Correct	2 ms	760 KB	Output is correct
21	Correct	4 ms	760 KB	Output is correct
22	Correct	3 ms	760 KB	Output is correct
23	Correct	3 ms	760 KB	Output is correct
24	Correct	2 ms	760 KB	Output is correct
25	Correct	5 ms	760 KB	Output is correct
26	Correct	6 ms	760 KB	Output is correct
27	Correct	14 ms	760 KB	Output is correct
28	Correct	8 ms	760 KB	Output is correct
29	Correct	5 ms	760 KB	Output is correct
30	Correct	42 ms	760 KB	Output is correct
31	Correct	65 ms	760 KB	Output is correct
32	Correct	65 ms	764 KB	Output is correct
33	Correct	3 ms	764 KB	Output is correct
34	Correct	70 ms	764 KB	Output is correct
35	Correct	52 ms	764 KB	Output is correct
36	Correct	21 ms	764 KB	Output is correct

Subtask #3
0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	764 KB	Output is correct
2	Correct	2 ms	764 KB	Output is correct
3	Correct	2 ms	764 KB	Output is correct
4	Correct	2 ms	764 KB	Output is correct
5	Correct	2 ms	764 KB	Output is correct
6	Correct	6 ms	764 KB	Output is correct
7	Correct	3 ms	764 KB	Output is correct
8	Correct	2 ms	764 KB	Output is correct
9	Correct	3 ms	764 KB	Output is correct
10	Correct	3 ms	764 KB	Output is correct
11	Correct	2 ms	764 KB	Output is correct
12	Correct	2 ms	764 KB	Output is correct
13	Correct	10 ms	764 KB	Output is correct
14	Correct	13 ms	764 KB	Output is correct
15	Correct	7 ms	764 KB	Output is correct
16	Correct	6 ms	764 KB	Output is correct
17	Correct	39 ms	764 KB	Output is correct
18	Correct	67 ms	764 KB	Output is correct
19	Correct	67 ms	764 KB	Output is correct
20	Correct	2 ms	764 KB	Output is correct
21	Correct	66 ms	764 KB	Output is correct
22	Correct	51 ms	764 KB	Output is correct
23	Correct	21 ms	764 KB	Output is correct
24	Correct	71 ms	764 KB	Output is correct
25	Correct	32 ms	764 KB	Output is correct
26	Correct	204 ms	764 KB	Output is correct
27	Execution timed out	1076 ms	764 KB	Time limit exceeded
28	Halted	0 ms	0 KB	-

Subtask #4
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	764 KB	Output is correct
2	Correct	2 ms	764 KB	Output is correct
3	Correct	2 ms	764 KB	Output is correct
4	Correct	2 ms	764 KB	Output is correct
5	Correct	2 ms	764 KB	Output is correct
6	Correct	6 ms	764 KB	Output is correct
7	Correct	2 ms	764 KB	Output is correct
8	Correct	2 ms	764 KB	Output is correct
9	Correct	2 ms	764 KB	Output is correct
10	Correct	2 ms	764 KB	Output is correct
11	Correct	2 ms	764 KB	Output is correct
12	Correct	3 ms	764 KB	Output is correct
13	Correct	12 ms	764 KB	Output is correct
14	Correct	2 ms	764 KB	Output is correct
15	Correct	2 ms	764 KB	Output is correct
16	Correct	2 ms	764 KB	Output is correct
17	Correct	2 ms	764 KB	Output is correct
18	Correct	2 ms	764 KB	Output is correct
19	Correct	2 ms	764 KB	Output is correct
20	Correct	2 ms	764 KB	Output is correct
21	Correct	3 ms	764 KB	Output is correct
22	Correct	3 ms	764 KB	Output is correct
23	Correct	3 ms	764 KB	Output is correct
24	Correct	2 ms	764 KB	Output is correct
25	Correct	3 ms	764 KB	Output is correct
26	Correct	5 ms	764 KB	Output is correct
27	Correct	2 ms	764 KB	Output is correct
28	Correct	2 ms	764 KB	Output is correct
29	Correct	3 ms	764 KB	Output is correct
30	Correct	2 ms	764 KB	Output is correct
31	Correct	3 ms	764 KB	Output is correct
32	Correct	2 ms	764 KB	Output is correct
33	Correct	5 ms	764 KB	Output is correct
34	Correct	11 ms	764 KB	Output is correct
35	Correct	2 ms	764 KB	Output is correct
36	Correct	13 ms	764 KB	Output is correct
37	Correct	14 ms	764 KB	Output is correct
38	Correct	7 ms	764 KB	Output is correct
39	Correct	6 ms	764 KB	Output is correct
40	Correct	46 ms	764 KB	Output is correct
41	Correct	68 ms	764 KB	Output is correct
42	Correct	68 ms	764 KB	Output is correct
43	Correct	3 ms	764 KB	Output is correct
44	Correct	69 ms	764 KB	Output is correct
45	Correct	49 ms	764 KB	Output is correct
46	Correct	20 ms	764 KB	Output is correct
47	Correct	68 ms	764 KB	Output is correct
48	Correct	35 ms	764 KB	Output is correct
49	Correct	205 ms	764 KB	Output is correct
50	Execution timed out	1069 ms	764 KB	Time limit exceeded
51	Halted	0 ms	0 KB	-

Subtask #5
0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	764 KB	Output is correct
2	Correct	2 ms	764 KB	Output is correct
3	Correct	2 ms	764 KB	Output is correct
4	Correct	2 ms	764 KB	Output is correct
5	Correct	2 ms	764 KB	Output is correct
6	Correct	5 ms	764 KB	Output is correct
7	Correct	2 ms	764 KB	Output is correct
8	Correct	2 ms	764 KB	Output is correct
9	Correct	2 ms	764 KB	Output is correct
10	Correct	2 ms	764 KB	Output is correct
11	Correct	2 ms	764 KB	Output is correct
12	Correct	3 ms	764 KB	Output is correct
13	Correct	11 ms	764 KB	Output is correct
14	Correct	2 ms	764 KB	Output is correct
15	Correct	2 ms	764 KB	Output is correct
16	Correct	3 ms	764 KB	Output is correct
17	Correct	2 ms	764 KB	Output is correct
18	Correct	3 ms	764 KB	Output is correct
19	Correct	2 ms	764 KB	Output is correct
20	Correct	6 ms	764 KB	Output is correct
21	Correct	11 ms	764 KB	Output is correct
22	Correct	2 ms	764 KB	Output is correct
23	Correct	14 ms	764 KB	Output is correct
24	Correct	13 ms	764 KB	Output is correct
25	Correct	7 ms	764 KB	Output is correct
26	Correct	6 ms	764 KB	Output is correct
27	Correct	43 ms	764 KB	Output is correct
28	Correct	64 ms	764 KB	Output is correct
29	Correct	68 ms	764 KB	Output is correct
30	Correct	3 ms	764 KB	Output is correct
31	Correct	67 ms	764 KB	Output is correct
32	Correct	51 ms	764 KB	Output is correct
33	Correct	21 ms	764 KB	Output is correct
34	Correct	71 ms	764 KB	Output is correct
35	Correct	35 ms	764 KB	Output is correct
36	Correct	210 ms	764 KB	Output is correct
37	Execution timed out	1080 ms	764 KB	Time limit exceeded
38	Halted	0 ms	0 KB	-

답안 #77304

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 16.0 / 16.0

Subtask #3 0 / 21.0

Subtask #4 0 / 25.0

Subtask #5 0 / 29.0

Subtask #1
9.0 / 9.0

Subtask #2
16.0 / 16.0

Subtask #3
0 / 21.0

Subtask #4
0 / 25.0

Subtask #5
0 / 29.0