Submission #256088

#	Time	Username	Problem	Language	Result	Execution time	Memory
256088		fedoseevtimofey	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	124 ms	512 KiB

sculpture

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <iomanip>
#include <functional>
#include <cassert>
 
using namespace std;
 
typedef long long ll;
 
int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif
  int n, a, b;
  cin >> n >> a >> b;
  vector <int> v(n);
  for (int i = 0; i < n; ++i) cin >> v[i];
  vector <ll> pref(n + 1);
  for (int i = 0; i < n; ++i) {
    pref[i + 1] = pref[i] + v[i];
  }

  auto get = [&] (int l, int r) {
    return pref[r + 1] - pref[l];
  };

  if (n <= 200) {
    auto can = [&] (ll mask) {
      vector <vector <int>> dp(n + 1, vector <int> (n + 1));
      dp[0][0] = 1; 
      for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
          for (int k = i; k < n; ++k) {
            ll sm = get(i, k);
            if ((sm & mask) == 0) {
              dp[k + 1][j + 1] |= dp[i][j];
            }
          }
        }
      }
      bool ok = false;
      for (int x = a; x <= b; ++x) {
        ok |= dp[n][x];
      }
      return ok;
    };
    ll mask = 0;
    ll ans = 0;
    for (int b = 60; b >= 0; --b) {
      if (can(mask + (1LL << b))) {
        mask += (1LL << b);
      } else {
        ans += (1LL << b);
      }
    }
    cout << ans << '\n';
  } else {
    auto can = [&] (ll mask) {
      vector <int> dp(n + 1, (int)1e9);
      dp[0] = 0;
      for (int i = 0; i < n; ++i) {
        for (int j = i; j < n; ++j) {
          ll sm = get(i, j);
          if ((sm & mask) == 0) {
            dp[j + 1] = min(dp[j + 1], dp[i] + 1);
          }
        }
      }
      return (dp[n] <= b);
    };
    ll mask = 0;
    ll ans = 0;
    for (int b = 60; b >= 0; --b) {
      if (can(mask + (1LL << b))) {
        mask += (1LL << b);
      } else {
        ans += (1LL << b);
      }
    }
    cout << ans << '\n';

  }
}

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