제출 #43581

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
43581		RezwanArefin01	Bali Sculptures (APIO15_sculpture)	C++14	16 / 100	1056 ms	12264 KiB

sculpture

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii; 

unordered_map<int, unordered_map<int, int> > dp[101]; 
int a[110], p[110], n; 

int f(int i, int k, int o) {
	if(k > i) return 1e9; 
	if(k == 1) return p[i] | o;

	if(dp[i].count(k)) if(dp[i][k].count(o)) return dp[i][k][o];

	int &ret = dp[i][k][o];

	int sum = a[i];
	ret = 1e9;
	for(int j = i - 1; j >= 1; j--) {
		ret = min(ret, f(j, k - 1, sum | o) | sum | o); 
		sum += a[j];
	}
	return ret;
}
int main(int argc, char const *argv[]) {
#ifdef LOCAL_TESTING
	freopen("in", "r", stdin);
#endif
	int n, l, r;
	cin >> n >> l >> r; 
	for(int i = 1; i <= n; i++) {
		cin >> a[i]; p[i] = p[i - 1] + a[i];
	}

	int ans = 1e9;

	for(int i = l; i <= r; i++) {
		ans = min(ans, f(n, i, 0));
	}
	cout << ans << endl;

}

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