Submission #1311100

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311100		altern23	Bali Sculptures (APIO15_sculpture)	C++20	50 / 100	170 ms	588 KiB

sculpture

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

const ll INF = 1e18;

int main(){
      ios_base::sync_with_stdio(0); cin.tie(0);
      int tc = 1;	
      // cin >> tc;
      for (;tc--;) {
            ll N, A, B; cin >> N >> A >> B;
            vector <ll> Y(N + 5);
            for (int i = 1; i <= N; i++) {
                  cin >> Y[i];
            }
            
            ll ans = 0, del = 0;
            for (int bit = 60; bit >= 0; --bit) {
                  // try to not include bit i
                  vector <ll> dp(N + 5, INF);
                  dp[0] = 0;
                  del += (1LL << bit);
                  for (int i = 1; i <= N; i++) {
                        ll sm = 0;
                        for (int j = i; j >= 1; --j) {
                              sm += Y[j];
                              if (!(sm & del)) {
                                    // cout << i << " " << j << " " << bit << "\n";
                                    dp[i] = min(dp[i], dp[j - 1] + 1);
                              }
                        }
                  }
                  if (dp[N] > B) {
                        ans += (1LL << bit);
                        del -= (1LL << bit);
                  }
                  // cout << del << "\n";
            }

            cout << ans << "\n";
      }
}

/*
Bali Sculptures
*/

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