Submission #1028524

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028524		vjudge1	Bali Sculptures (APIO15_sculpture)	C++17	71 / 100	1034 ms	2396 KiB

sculpture

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll inf = 1e18, N = 2000 + 10;
int n, a, b;
vector<int> v(N);

bool check(ll exp)
{
  bool dp[1 + n][1 + b];
  memset(dp, false, sizeof(dp));
  dp[0][0] = true;

  for(int i = 0; i < n; i ++)
    for(int j = 0; j < b; j ++)
      {
	if(!dp[i][j]) continue;
	ll sm = 0;
	for(int k = i + 1; k <= n; k++)
	  {
	    sm += v[k];
	    if(sm & (~exp)) continue;
	    dp[k][j + 1] = true;
	  }
      }

  bool ans = false;
  for(int i = a; i <= b; i ++) ans |= dp[n][i];
  return ans;
}

int main()
{
  cin >> n >> a >> b;
  for(int i = 1; i <= n; i ++)
    cin >> v[i];

  
  ll ans = 0;
  for(int i : v) ans += i;

  int b = 64 - __builtin_clzll(ans);
  ans = (1LL << b) - 1;

  for(int i = 63; i >= 0; i --)
    {
      if((1LL << i) & ans)
	{
	  ans -= (1LL << i);
	  if(!check(ans))
	    ans += (1LL << i);
	}
    }
  cout << ans << endl;
  return 0;
}

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