Submission #1311102

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311102		altern23	Bali Sculptures (APIO15_sculpture)	C++20	21 / 100	6 ms	648 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];
            }

            if (N <= 100) {
                  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";
            }
            else {
                  ll ans = 0, del = 0;
                  vector <vector<ll>> dp(N + 5, vector <ll> (B + 5));
                  for (int bit = 60; bit >= 0; --bit) {
                        dp[0][0] = 1;
                        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)) {
                                          for (int k = 1; k <= i; k++) {
                                                dp[i][k] |= dp[j - 1][k - 1];
                                          }
                                    }
                              }
                        }
                        
                        bool fnd = 0;
                        for (int i = A; i <= B; i++) {
                              if (dp[N][i]) {
                                    fnd = 1;
                                    break;
                              }
                        }

                        if (!fnd) {
                              ans += (1LL << bit);
                              del -= (1LL << bit);
                        }

                        for (int i = 1; i <= N; i++) {
                              for (int j = 0; j <= i; j++) dp[i][j] = 0;
                        }
                  }

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

/*
Bali Sculptures
*/

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