oj.uz

Submission #104759

# Submission time Handle Problem Language Result Execution time Memory
104759 2019-04-09T06:58:52 Z ekrem Bali Sculptures (APIO15_sculpture) C++
0 / 100
 34 ms 31868 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 31736 KB Output is correct
2 Incorrect 29 ms 31868 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 31736 KB Output is correct
2 Incorrect 29 ms 31736 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 31736 KB Output is correct
2 Incorrect 28 ms 31736 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 31712 KB Output is correct
2 Incorrect 31 ms 31764 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 31744 KB Output is correct
2 Incorrect 34 ms 31864 KB Output isn't correct
3 Halted 0 ms 0 KB -