Submission #104759

#	Time	Username	Problem	Language	Result	Execution time	Memory
104759		ekrem	Bali Sculptures (APIO15_sculpture)	C++98	0 / 100	34 ms	31868 KiB

sculpture

#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define inf 1000000000000000007
#define N 2005
using namespace std;

typedef long long ll;

ll n, X, Y, ans = inf, a[N], pre[N], dp[N][N];

void dfs(ll i, ll x, ll top, ll kac){
	if(i == n + 1){
		if(top != 0)
			return;
		if(kac <= Y and kac >= X)
			ans = min(ans, x);
		return;
	}
	top += a[i];
	dfs(i + 1, x|top, 0, kac + 1);
	dfs(i + 1, x, top, kac);
}

ll f(ll ind, ll kac){
	ll &r = dp[ind][kac];
	if(r != -1)
		return r;
	if(ind == 0)
		return r = (kac == 0)?0:inf;
	r = inf;
	for(int i = 0; i < ind; i++)
		r = min(r, f(i, kac - 1)|(pre[ind] - pre[i]));
	return r;
}

int main() {
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	memset(dp, -1, sizeof dp);
	scanf("%lld %lld %lld",&n ,&X ,&Y);
	for(int i = 1; i <= n; i++){
		scanf("%lld",a + i);
		pre[i] = pre[i - 1] + a[i];
	}

	// dfs(1, 0, 0, 0);

	// for(int i = 1; i <= n; i++){
	// 	dp[i][0] = inf;
	// 	dp[0][i] = inf;
	// }

	// for(int i = 1; i <= n; i++)
	// 	for(int k = 1; k <= n; k++){
	// 		dp[i][k] = inf;
	// 		for(int j = i - 1; j >= 0; j--)
	// 			dp[i][k] = min(dp[i][k], ((pre[i] - pre[j])|dp[j][k - 1]) );
	// 		cout << i << " " << k << " -> " << dp[i][k] << endl;
	// 	}
	for(int i = X; i <= Y; i++)
		ans = min(ans, f(n, i));
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld %lld",&n ,&X ,&Y);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",a + i);
   ~~~~~^~~~~~~~~~~~~~

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