Submission #31086

#	Time	Username	Problem	Language	Result	Execution time	Memory
31086		WhipppedCream	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	126 ms	2084 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 dp2[105][105];
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 g(int u, int rem, LL targ)
{
	if(u == n+1 && rem == 0) return 1;
	if(u == n+1 || rem == 0) return 0;
	if(dp2[u][rem] != -1) return dp2[u][rem];
	dp2[u][rem] = 0;
	for(int i = u; i<= n; i++)
	{
		LL w = ask(u, i);
		if((targ|w)> targ) continue;
		dp2[u][rem] |= g(i+1, rem-1, targ);
	}
	return dp2[u][rem];
}
bool works2(LL trie)
{
	memset(dp2, -1, sizeof dp2);
	for(int i = a; i<= b; i++) if(g(1, i, trie)) 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(a == 1)
		{
			if(works(want)) cur = want;
		}
		else
		{
			if(works2(want)) cur = want;
		}
	}
	printf("%lld\n", cur);
	return 0;
}

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:61: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:64:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", qs+i);
                      ^

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