Submission #230479

#	Time	Username	Problem	Language	Result	Execution time	Memory
230479		AlexLuchianov	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	161 ms	512 KiB

sculpture

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>
#include <bitset>

using namespace std;

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 2000;
ll v[1 + nmax], sum[1 + nmax];
int dp[1 + nmax];

bool valid(int x, int y, ll lim){
  return ((lim | (sum[y] - sum[x - 1])) == lim);
}

bitset<1 + nmax> dp2[5 + nmax / 20];

/*
6 1 3
8 1 2 1 5 4
*/

bool check(int n, int a, int b, ll lim){
  if(a == 1){
    dp[0] = 0;
    for(int i = 1;i <= n; i++) {
      dp[i] = n + 1;
      for(int j = i; 1 <= j; j--)
        if(valid(j, i, lim) == 1)
          dp[i] = min(dp[i], dp[j - 1] + 1);
    }
    return (dp[n] <= b);
  } else {
    for(int i = 0;i <= n; i++)
      dp2[i] = dp2[n + 1];
    dp2[0][0] = 1;
    for(int i = 1; i <= n; i++)
      for(int j = i; 1 <= j; j--)
        if(valid(j, i, lim) == 1)
          dp2[i] |= (dp2[j - 1]<<1);
    for(int i = a; i <= b; i++)
      if(dp2[n][i] == 1)
        return 1;
    return 0;
  }
}

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  int n, a, b;
  cin >> n >> a >> b;
  for(int i = 1;i <= n; i++) {
    cin >> v[i];
    sum[i] = sum[i - 1] + v[i];
  }
  ll sol = (1LL << 50) - 1;
  for(int i = 49; 0 <= i; i--)
    if(check(n, a, b, sol ^ (1LL << i)) == 1)
      sol ^= (1LL << i);
  cout << sol;
  return 0;
}

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