Submission #1257020

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257020		xardkodych	Bali Sculptures (APIO15_sculpture)	C++20	71 / 100	907 ms	956 KiB

sculpture

// #pragma optimize("Ofast")
#include "bits/stdc++.h"
#define int long long
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define em emplace_back
#define mp make_pair
#define F first
#define S second

using namespace std;
template<class C>
using vec = vector<C>;
using vi = vector<int>;
using vpi = vector<pair<int, int> >;
using pii = pair<int, int>;
#ifdef LOCAL
const int N = 11;
#else
const int N = 2001;
#endif
int n, l, r;
int a[N];
bitset<N> dp[N];

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> l >> r;
  for (int i = 0; i < n; i++)
    cin >> a[i];
  int mask = 0;
  for (int b = 38; b >= 0; b--) {
    memset(dp, 0, sizeof dp);
    dp[0][0] = true;
    for (int i = 0; i < n; i++) {
      int sum = 0;
      for (int j = i; j >= 0; j--) {
        sum += a[j];
        bool check = ((sum >> b) & (~mask >> b)) == 0;
        if (check) {
          dp[i + 1] |= dp[j] << 1;
        }
      }
    }
    mask += 1ll << b;
    for (int i = l; i <= r; i++) {
      if (dp[n][i]) {
        mask -= 1ll << b;
        break;
      }
    }
  }
  cout << mask << '\n';
}

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