Submission #284676

#	Time	Username	Problem	Language	Result	Execution time	Memory
284676		triplem5ds	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	105 ms	512 KiB

sculpture

#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")

#include "bits/stdc++.h"
using namespace std;

#define pb push_back
#define F first
#define S second
#define f(i,a,b)  for(int i = a; i < b; i++)
#define endl '\n'

using ll = long long;
using db = long double;
using ii = pair<int, int>;

const int N = 2e5 + 5, LG = 19, MOD = 1e9 + 7;
const int SQ =225;
const long double EPS = 1e-7;
ll a[2005];
int dp[2005];
int dp2[105][105];
int n, l, r;
bool solve(ll ans, int bit){
  if(l == 1){
    memset(dp,63,sizeof dp);
    dp[0] = 0;
    f(i,1,n+1){
      f(j,0,i){
        ll sum = a[i] - a[j];
        if((sum | ans) < (ans | (1ll << bit)))
          dp[i] = min(dp[i], dp[j] + 1);
      }
    }
    return dp[n] > r;
  } else {
    memset(dp2,0,sizeof dp2);
    dp2[0][0] = 1;
    f(cnt,1,n+1)
      f(i,1,n+1)
        f(j,0,i){
          ll sum = a[i] - a[j];
          if((sum | ans) < (ans | (1ll << bit)))
            dp2[i][cnt] |= dp2[j][cnt - 1];
        }
    f(i,l,r+1)
      if(dp2[n][i])
        return false;
    return true;
  }
}
int32_t main(){
//#ifdef ONLINE_JUDGE
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//#endif

  cin >> n >> l >> r;

  f(i,1,n+1)
    cin >> a[i], a[i] += a[i-1];

 ll ans = 0;

 for(int bit = 40; bit >= 0; --bit)
    if(solve(ans, bit))
      ans += 1ll << bit;

 cout << ans << endl;

  return 0;
}

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