Submission #1131056

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131056		Champ_Naman	Bali Sculptures (APIO15_sculpture)	C++20	100 / 100	102 ms	516 KiB

sculpture

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 1e18
#define nl '\n'

int n, a, b;

inline void solve(){
   int c[n+1], dp[n+1];
   for(int i=1; i<=n; i++) cin>>c[i];

   int ans = (1ll<<42) - 1;

   for(int bit=41; bit>=0; bit--){
      ans -= (1ll<<bit);

      dp[0] = 0;
      for(int i=1; i<=n; i++){
         dp[i] = inf;

         int sum = 0;
         for(int j=i; j>0; j--){
            sum += c[j];
            if((sum | ans) == ans) dp[i] = min(dp[i], dp[j-1] + 1);
         }
      }

      if(dp[n] > b) ans += (1ll<<bit);
   }

   cout<<ans;
}

int dp[101][101];

inline void solve2(){
   int c[n+1];
   for(int i=1; i<=n; i++) cin>>c[i];

   int ans = (1ll<<42) - 1;

   for(int bit=41; bit>=0; bit--){
      ans -= (1ll<<bit);

      dp[0][0] = 1;
      for(int i=1; i<=n; i++){
         for(int k=1; k<=b; k++){
            dp[i][k] = 0;
            
            int sum = 0;
            for(int j=i; j>0; j--){
               sum += c[j];
               if((sum | ans) == ans and dp[j-1][k-1]) dp[i][k] = 1;
            }
         }
      }

      int tf = 0;
      for(int i=a; i<=b; i++) if(dp[n][i]) tf = 1;
      if(!tf) ans += (1ll<<bit);
   }

   cout<<ans;
}

signed main(){
   ios_base::sync_with_stdio(0);
   cin.tie(NULL);cout.tie(NULL);

   cin>>n>>a>>b;
   if(a == 1) solve();
   else solve2();

   return 0;
}

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