제출 #1130340

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1130340		am_aadvik	Bali Sculptures (APIO15_sculpture)	C++20	16 / 100	280 ms	50248 KiB

sculpture

#include <iostream>
#include<vector>
#include<string>
#include<queue>
#include<map>
#include<set>
#include<algorithm>
#include<math.h>
#define int long long
const int debug = 0;
const int inf = 1e17;
const int maxn = 300005;
const int mod = (int)1e9 + 7;
using namespace std;


int arr[maxn], dp[55][55][2005];
void problemB()
{
	int n, a, b;
	cin >> n >> a >> b;
	for (int i = 0; i < n; ++i)
		cin >> arr[i];

	if (n == 1) cout << arr[0] << endl;
	else if ((n == 2) || ((a == b) && (b == n)) || ((a == b) && (a == 1)))
	{
		int case1 = arr[0], case2 = arr[0];
		for (int i = 1; i < n; ++i)
			case1 |= arr[i], case2 += arr[i];

		if ((a == b) && (b == n))
			cout << case1 << endl;
		else if ((a == 1) && (b == a))
			cout << case2 << endl;
		else
			cout << min(case1, case2) << endl;
	}
	else
	{
		for (int i = 0; i <= n; ++i)
			for (int j = 0; j <= n; ++j)
				for (int x = 0; x <= 2000; ++x)
					dp[i][j][x] = inf;

		for (int i = a; i <= b; ++i)
			for (int x = 0; x <= 2000; ++x)
				dp[n][i][x] = x;

		for (int i = n - 1; i >= 0; --i)
			for (int j = 0; j <= n; ++j)
				for (int cor = 0; cor <= 2000; ++cor)
				{
					int cs = arr[i];
					for (int x = i + 1; x <= n; cs += arr[x], ++x)
						dp[i][j][cor] = min(dp[i][j][cor], dp[x][j + 1][cor | cs]);
				}
		cout << dp[0][0][0] << endl;
	}
}

int32_t main()
{
	int t = 1;
	while (t--)
	{
		problemB();
	}
}

• Subtask 1: 0 / 9
• Subtask 2: 16 / 16
• Subtask 3: 0 / 21
• Subtask 4: 0 / 25
• Subtask 5: 0 / 29