Submission #31085

#	Time	Username	Problem	Language	Result	Execution time	Memory
31085		WhipppedCream	Bali Sculptures (APIO15_sculpture)	C++14	50 / 100	116 ms	2044 KiB

sculpture

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector< ii > vii;
typedef long long LL;
LL qs[2005];
LL ask(int a, int b)
{
	return qs[b]-qs[a-1];
}
int dp[2005];
int n, a, b;
int f(int u, LL targ)
{
	if(u == n+1) return 0;
	if(dp[u] != -1) return dp[u];
	dp[u] = 1e9;
	for(int i = u; i<= n; i++)
	{
		LL w = ask(u, i);
		if((targ|w)> targ) continue;
		dp[u] = min(dp[u], 1+f(i+1, targ));
	}
	return dp[u];
}
bool works(LL trie)
{
	memset(dp, -1, sizeof dp);
	int ans = f(1, trie);
	if(ans<= b) return 1;
	return 0;
}
int main()
{
	scanf("%d %d %d", &n, &a, &b);
	for(int i = 1; i<= n; i++)
	{
		scanf("%lld", qs+i);
		qs[i] += qs[i-1];
	}
	LL cur = (1LL<<41)-1;
	for(int i = 40; i>= 0; i--)
	{
		LL want = cur-(1LL<<i);
		if(works(want)) cur = want;
	}
	printf("%lld\n", cur);
	return 0;
}

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:40:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &a, &b);
                               ^
sculpture.cpp:43:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", qs+i);
                      ^

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