Submission #1196029

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196029		meisgood	Bali Sculptures (APIO15_sculpture)	C++20	50 / 100	367 ms	21832 KiB

sculpture

#include <bits/stdc++.h>
using namespace std;
#define int long long
int arr[2003] ;
int ps[2003] ;
int n,aa,bb ;
int dist[2003] ;
bool vis[2003] ;
bool check(int x){
  vector <int> adj[2003] ;
  int i,j ;
  for (i = 0 ; i < 2003 ; i ++) dist[i]=INT_MAX,vis[i]=0 ;
  for (i = 0 ; i <= n ; i ++){
    for (j = 0 ; j < i ; j ++){
      if ((x|(ps[i]-ps[j]))==x){
        adj[j].push_back(i) ;
        // cout << x << endl ;
        // cout << (x|(ps[i]-ps[j])) << endl ;
        // cout << j << i << (ps[i]-ps[j]) << endl ;
      }
    }
  }
  queue <int> q ;
  q.push(0) ;
  dist[0]=0 ;
  while (!q.empty()){
    auto x=q.front() ;
    q.pop() ;
    if (vis[x]) continue ;
    vis[x]=1 ;
    for (auto a : adj[x]){
      if (dist[a]>dist[x]+1&&!vis[a]) q.push(a),dist[a]=dist[x]+1 ;
    }
  }
  if (dist[n]<=bb) return 1 ;
  return 0 ;
}
signed main() {
  int i,j ;
  cin >> n >> aa >> bb ;
  for (i = 1 ; i <= n ; i ++){
    cin >> arr[i] ;
    ps[i]=ps[i-1]+arr[i] ;
  }
  if (aa!=1){
    int dp[103][103] ;
    for (i = 0 ; i < 103 ; i ++) for (j = 0 ; j < 103 ; j ++) dp[i][j]=LLONG_MAX/4 ;
    dp[0][0]=0 ;
    for (i = 1 ; i <= n ; i ++){
      for (j = i ; j <= n ; j ++){
        for (int k = 0 ; k < j ; k ++){
          dp[i][j]=min(dp[i][j],dp[i-1][k]|(ps[j]-ps[k])) ;
        }
      }
    }
    int mn=LLONG_MAX/4 ;
    for (i = aa ; i <= bb ; i ++){
      mn=min(mn,dp[i][n]) ;
    }
    cout << mn << endl ;
  }
  else {
    // cout << check(11) << endl ;
    int x=(1ll<<60ll)-1ll ;
    for (i = 59 ; i >= 0 ; i --){
      // cout << check(x) << endl ;
      if (check(x^(1ll<<i))) x^=(1ll<<i) ;
    }
    cout << x << endl ;
  }
  return 0;
}

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