Submission #225120

#	Time	Username	Problem	Language	Result	Execution time	Memory
225120		rama_pang	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	130 ms	504 KiB

sculpture

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

int N, A, B;
lint Y[2005];
int dp_opt[2005];
bitset<105> dp_bitset[105]; // dp_bitset[pos][groups]

bool Calc(lint mask) {
  dp_opt[N] = 0;
  if (A > 1) for (int i = A; i <= B; i++) {
    dp_bitset[N][i] = 1;
  }

  for (int pos = N - 1; pos >= 0; pos--) {
    dp_opt[pos] = B + 1;
    if (A > 1) dp_bitset[pos] = 0;

    lint sum = 0;
    for (int nxt = pos; nxt < N; nxt++) {
      sum += Y[nxt];
      if ((sum | mask) == mask) {
        dp_opt[pos] = min(dp_opt[pos], dp_opt[nxt + 1] + 1);
        if (A > 1) dp_bitset[pos] |= dp_bitset[nxt + 1] >> 1;
      }
    }
  }

  return A > 1 ? dp_bitset[0][0] : dp_opt[0] <= B;
}

lint 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: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 21 / 21
• Subtask 4: 25 / 25
• Subtask 5: 29 / 29