제출 #225108

#제출 시각아이디문제언어결과실행 시간메모리
225108rama_pangBali Sculptures (APIO15_sculpture)C++14
71 / 100
1084 ms1016 KiB
#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) {
  for (int i = A; i <= B; i++) {
    dp[N][i] = 1;
  }
  for (int pos = N - 1; pos >= 0; pos--) {
    dp[pos] = 0;
    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];
}

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...