Submission #1009715

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009715		asdfgrace	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	78 ms	600 KiB

sculpture

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

#define dbg(x) x
#define prt(x) dbg(cerr << x)
#define pv(x) dbg(cerr << #x << " = " << x << '\n')
#define pv2(x) dbg(cerr << #x << " = " << x.first << ',' << x.second << '\n')
#define parr(x) dbg(prt(#x << " = { "); for (auto y : x) prt(y << ' '); prt("}\n");)
#define parr2(x) dbg(prt(#x << " = { "); for (auto [y, z] : x) prt(y << ',' << z << "  "); prt("}\n");)
#define parr2d(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr(arr);} prt('\n'));
#define parr2d2(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr2(arr);} prt('\n'));

/*
a <= x <= b subsegments
MINIMIZE bitwise or of sums
either n^2 and a=1 or n^3 and a is maybe not 1

st with a>=1:
can we iterate thru bits
the idea:
given previous restrictions on bits that have to be 0
(others can be 1 & are impossible to make 0)
can we make it good for this
for (i)
for (last i)
if the sum is good
for all dp[last_i][j] that are true, dp[i][j + 1] is true
complexity = n^2 * b * log(s)


st with a==1:
iterate thru sums bc only go up to like 2000
for each num find if you can have or <= num
by doing dp
bc a=1
can just track possible/not and min # of segments needed
at every ind
complexity = n^2 * log(s) ---> was gonna be max_s but turns out log(s) works
can this pass st5
if we binary search the maximum or
or do bit by bit
yeah
*/

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int n, a, b;
  cin >> n >> a >> b;
  vector<long long> s(n);
  long long sum = 0;
  for (int i = 0; i < n; i++) {
    cin >> s[i];
    sum += s[i];
  }
  long long p2 = 1ll, mxbit = 0;
  while (p2 < sum) {
    p2 <<= 1; mxbit++;
  }
  long long req = (1ll << (mxbit + 1)) - 1;
  if (a == 1) {
    for (int bit = mxbit; bit >= 0; bit--) {
      req -= (1ll << bit);
      vector<long long> best(n + 1, 1e9);
      best[0] = 0;
      for (int i = 1; i <= n; i++) {
        long long lst = 0;
        for (int j = i - 1; j >= 0; j--) {
          lst += s[j];
          if ((req | lst) == req) {
            best[i] = min(best[i], best[j] + 1);
          }
        }
      }
      if (best[n] > b) {
        req += (1ll << bit);
      }
    }
  } else {
    for (int bit = mxbit; bit >= 0; bit--) {
      req -= (1ll << bit);
      vector<vector<bool>> ok(n + 1, vector<bool>(b + 1, false));
      ok[0][0] = true;
      for (int i = 1; i <= n; i++) {
        long long lst = 0;
        for (int j = i - 1; j >= 0; j--) {
          lst += s[j];
          if ((req | lst) == req) {
            for (int k = 0; k < b; k++) {
              if (ok[j][k]) {
                ok[i][k + 1] = true;
              }
            }
          }
        }
      }
      bool good = false;
      for (int i = a; i <= b; i++) {
        if (ok[n][i]) {
          good =  true;
          break;
        }
      }
      if (!good) {
        req += (1ll << bit);
      }
    }
  }
  cout << req << '\n';
}

/*
any observations help

check every line
IF YOUR LINES AREN'T WRONG
CHECK IF YOUR LINES ARE IN THE RIGHT ORDER

NEVER GIVE UP
*/

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