Submission #225120

#TimeUsernameProblemLanguageResultExecution timeMemory
225120rama_pangBali Sculptures (APIO15_sculpture)C++14
100 / 100
130 ms504 KiB
#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;
}
#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...