Submission #23095

#	Time	Username	Problem	Language	Result	Execution time	Memory
23095		themastermind	Bali Sculptures (APIO15_sculpture)	C++14	71 / 100	1000 ms	6156 KiB

sculpture

#include <bits/stdc++.h>
#define forinc(i,a,b) for(int i = a, _key = b; i <= _key; ++i)
#define fordec(i,a,b) for(int i = a, _key = b; i >= _key; --i)
#define fori(i,n) for(int i = 0, _key = n; i < _key; ++i)
#define ford(i,n) for(int i = n - 1; i >= 0; --i)
#define forvct(i,v) for(int i = 0, _key = v.size(); i < _key; ++i)
#define sqr(x) ((ll)x) * (x)
#define task "sculpture"
#define st first
#define nd second
#define m_p make_pair
#define m_t make_tuple
#define p_b push_back
#define p_f push_front
#define pp_b pop_back
#define pp_f pop_front
#define sn string::npos
#define heap priority_queue
#define ll long long
#define db double
#define str string
#define eps 1e-10
#define nn 2010

using namespace std;

const ll oo = 1000000000000007LL;

ll n, A, B, a[nn], s[nn], res;
bool f[nn][nn];

bool comp(const ll x, const ll y)
{
   return (x | y) == x;
}

bool check(const int &t)
{
   ll x = res >> t;
   memset(f,false,sizeof f);
   forinc(i,1,n)
   {
      f[i][1] = comp(x,s[i]>>t);
      forinc(j,2,min((ll)i,B))
      {
         f[i][j] = false;
         forinc(ii,j-1,i-1)
            if (f[ii][j-1] && comp(x,(s[i]-s[ii])>>t))
            {
               f[i][j] = true;
               break;
            }
      }
   }
   forinc(i,A,B)
      if (f[n][i]) return true;
   return false;
}

int main()
{
   ios_base::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);
   //srand(time(NULL));
   //freopen(task".inp","r",stdin);
   //freopen(task".out","w",stdout);
   cin >> n >> A >> B;
   forinc(i,1,n)
   {
       cin >> a[i];
       s[i] = s[i-1] + a[i];
   }
   res = 0;
   ford(i,60)
      if (!check(i)) res |= (1LL << i);
   cout << res;
}

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