Submission #225103

#	Time	Username	Problem	Language	Result	Execution time	Memory
225103		rama_pang	Bali Sculptures (APIO15_sculpture)	C++14	37 / 100	30 ms	512 KiB

sculpture

#include <bits/stdc++.h>
using namespace std;
using lint = long long;

const int MAXN = 2005;
const int MAXB = 45;

int N, A, B;
lint Y[MAXN];
bitset<MAXN> dp[2005]; // dp[pos][groups]

bool Calc(lint mask) {
  dp[N] = 0;
  for (int i = A; i <= B; i++) {
    dp[N][i] = 1;
  }
  for (int i = 0; i < N; i++) {
    for (int j = 0; j <= B; j++) {
      dp[i][j] = 0;
    }
  }
  for (int pos = N - 1; pos >= 0; pos--) {
    lint sum = 0;
    for (int nxt = pos; nxt < N; nxt++) {
      sum += Y[nxt];
      if ((sum | mask) == mask) {
        dp[pos] |= dp[nxt + 1] >> 1;
      }
    }
  }

  return dp[0][0];
}

int Solve() {
  lint mask = (1ll << MAXB) - 1;
  for (lint j = MAXB - 1; j >= 0; j--) {
    if (Calc(mask - (1ll << j))) { // check if there is a grouping with cost as a subset of mask
      mask -= 1ll << j;
    }
  }
  return mask;
}

void Read() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  cin >> N >> A >> B;
  for (int i = 0; i < N; i++) {
    cin >> Y[i];
  }
}

int main() {
  Read();
  cout << Solve() << "\n";
  return 0;
}

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