제출 #1196036

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1196036		meisgood	Bali Sculptures (APIO15_sculpture)	C++20	100 / 100	282 ms	21688 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 ;
}
bool dp[103][103] ;
bool check2(int x){
  int i,j ;
  for (i = 0 ; i < 103 ; i ++) for (j = 0 ; j < 103 ; j ++) dp[i][j]=0 ;
  dp[0][0]=1 ;
  for (i = 1 ; i <= n ; i ++){
    for (j = 1 ; j <= n ; j ++){
      for (int k = 0 ; k < j ; k ++){
        if (((ps[j]-ps[k])|x)==x) dp[i][j]|=dp[i-1][k] ;
      }
    }
  }
  for (i = aa ; i <= bb ; i ++){
    if (dp[i][n]) 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 x=(1ll<<60ll)-1ll ;
    for (i = 59 ; i >= 0 ; i --){
      if (check2(x^(1ll<<i))) x^=(1ll<<i) ;
    }
    cout << x << 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: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 21 / 21
• Subtask 4: 25 / 25
• Subtask 5: 29 / 29