Submission #1028526

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028526		vjudge1	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	404 ms	1440 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);
bitset<N> mask[N], dp[N];

bool check(ll exp)
{
  bitset<N> dp[1 + b];
  for(int i = 0; i <= b; i ++)
    dp[i].reset();
  
  dp[0][0] = 1;

  for(int i = 1; i <= n; i ++)
    {
      bitset<N> mymask;
      mymask.reset();
      ll sm = 0;
      for(int j = i; j <= n; j ++)
	{
	  sm += v[j];
	  if(sm & (~exp)) continue;
	  mymask[j] = 1;
	}
      
      mask[i] = mymask;
    }

    for(int j = 0; j < b; j ++)
      for(int i = 0; i < n; i ++)
	{
	  if(dp[j][i] == 0) continue;
	  dp[j + 1] |= mask[i + 1];
	}

  bool ans = false;
  for(int i = a; i <= b; i ++) ans |= dp[i][n];
  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: 29 / 29