제출 #1028526

#제출 시각아이디문제언어결과실행 시간메모리
1028526vjudge1Bali Sculptures (APIO15_sculpture)C++17
100 / 100
404 ms1440 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...