Submission #524051

#	Time	Username	Problem	Language	Result	Execution time	Memory
524051		soeil	Bali Sculptures (APIO15_sculpture)	C++11	100 / 100	217 ms	16148 KiB

sculpture

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

#define siz(v) (int)(v).size()
#define all(v) (v).begin(),(v).end()
#define bit(n, k) (((n) >> (k)) & 1)

using ll = long long;

template <typename lhs> inline bool ckmin(lhs & a, lhs b) {
   return b < a ? a = b, true : false;
}

template <typename lhs> inline bool ckmax(lhs & a, lhs b) {
   return b > a ? a = b, true : false;
}

#define is(x) ((x | ans) == ans)

const int maxn = 2005, og = 46;
const ll hi = (1ll << og) - 1ll;
int n, A, B, arr[maxn], dp[maxn][maxn]; // {i, cnt}
ll ans = hi, sum[maxn];

void ca() {
   for (int b = og - 1; b >= 0; b--) {
      memset(dp, 0, sizeof dp);
      ans &= (hi - (1ll << b));
      for (int i = 0; i < n; i++) {
         dp[i][1] = is(sum[i]);
      }
      for (int i = 1; i < n; i++) {
         for (int j = 2; j <= B; j++) {
            ll s = 0;
            for (int x = i; x > 0; x--) {
               s += 1ll * arr[x];
               if (is(s)) {
                  dp[i][j] |= dp[x - 1][j - 1];
               }
            }
         }
      }
      int f = 0;
      for (int i = A; i <= B; i++) {
         if (dp[n - 1][i]) {
            f = 1;
            break;
         }
      }
      if (not f) {
         ans |= (1ll << b);
      }
   }
}

void cb() {
   for (int b = og - 1; b >= 0; b--) {
      memset(dp, 0x3F, sizeof dp);
      ans &= (hi - (1ll << b));
      if (is(arr[0])) {
         dp[0][0] = 1;
      }
      for (int i = 1; i < n; i++) {
         ll s = 0;
         for (int j = i; j >= 0; j--) {
            s += 1ll * arr[j];
            if (is(s)) {
               if (not j) {
                  dp[i][0] = 1;
                  continue;
               }
               ckmin(dp[i][0], 1 + dp[j - 1][0]);
            }
         }
      }
      if (dp[n - 1][0] > B) {
         ans |= (1ll << b);
      }
   }
}

void Main() {
   cin >> n >> A >> B;
   for (int i = 0; i < n; i++) {
      cin >> arr[i];
      sum[i] = (i ? sum[i - 1] : 0ll) + 1ll * arr[i];
   }
   if (A != 1) {
      ca();
   } else {
      cb();
   }
   cout << ans << '\n';
}

signed main() {
   ios_base::sync_with_stdio(false); cin.tie(0);
   int n = 1;
   // cin >> n;
   while (n--) {
      Main();
   }
   return 0;
}

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