Submission #23094

#	Time	Username	Problem	Language	Result	Execution time	Memory
23094		themastermind	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	126 ms	2216 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 task "sculpture"
#define st first
#define nd second
#define m_p make_pair
#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 ll long long
#define db double
#define str string
#define base 1000000007
#define nn 2010

using namespace std;

int n, a, b;
bool f1[110][110];
int f2[nn];
long long s[nn], key;

bool subset(const ll &x, const ll &y)
{
    return (x & y) == x;
}

void enter()
{
    cin >> n >> a >> b;
    b = min(b,n);
    int x;
    forinc(i,1,n)
    {
        cin >> x;
        s[i] = s[i-1] + x;
    }
}

bool check1(const int &p)
{
    memset(f1,false,sizeof f1);
    f1[0][0] = true;
    forinc(i,1,n)
        forinc(g,1,i)
            forinc(j,0,i-1)
                if (f1[j][g-1] && subset((s[i] - s[j]) >> p,key))
                {
                    f1[i][g] = true;
                    break;
                }
    forinc(g,a,b) if (f1[n][g]) return true;
    return false;
}

bool check2(const int &p)
{
    forinc(i,1,n) f2[i] = n + 1;
    forinc(i,1,n)
        forinc(j,0,i-1)
            if (subset((s[i] - s[j]) >> p,key))
                f2[i] = min(f2[i],f2[j] + 1);
    return (f2[n] <= b);
}

void process()
{
    key = 0;
    fordec(p,40,0)
    {
        key = (key << 1);
        if (!((a > 1 && check1(p)) || (a == 1 && check2(p)))) key |= 1;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    //freopen(task".inp","r",stdin);
    //freopen(task".out","w",stdout);
    enter();
    process();
    cout << key;
}

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