제출 #1319984

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1319984		NValchanov	Bali Sculptures (APIO15_sculpture)	C++20	100 / 100	81 ms	608 KiB

sculpture

#include <iostream>

using namespace std;

typedef long long llong;

const int MAXN = 2e3 + 10;
const int MAXLOG = 41;
const llong INF = 4e18 + 10;

int n, l, r;
int a[MAXN];
bool dp1[MAXN][MAXN];
llong dp2[MAXN];
llong pref[MAXN];

void read()
{
    cin >> n >> l >> r;

    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
}

void precomp()
{
    for(int i = 1; i <= n; i++)
    {
        pref[i] = pref[i - 1] + a[i];
    }
}

bool check1(llong x)
{
    for(int i = 0; i <= n; i++)
    {
        dp2[i] = INF;
    }

    dp2[0] = 0;

    for(int i = 1; i <= n; i++)
    {
        for(int k = 1; k <= i; k++)
        {
            llong sum = pref[i] - pref[k - 1];  

            if((x | sum) == x)
            {
                dp2[i] = min(dp2[i], dp2[k - 1] + 1);
            }
        }
    }

    return dp2[n] <= r;
}

bool check2(llong x)
{
    for(int i = 0; i <= n; i++)
    {
        for(int j = 0; j <= r; j++)
        {
            dp1[i][j] = false;
        }
    }

    dp1[0][0] = true;

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= r; j++)
        {
            for(int k = 1; k <= i; k++)
            {
                llong sum = pref[i] - pref[k - 1];

                if((x | sum) == x)
                {
                    dp1[i][j] |= dp1[k - 1][j - 1];
                }
            }
        }
    }

    for(int i = l; i <= r; i++)
    {
        if(dp1[n][i])
            return true;
    }

    return false;
}

void solve()
{
    llong ans = (1LL << MAXLOG) - 1;

    for(int bit = MAXLOG - 1; bit >= 0; bit--)
    {
        if(l == 1)
        {
            if(check1(ans - (1LL << bit)))
            {
                ans -= (1LL << bit);
            }
        }
        else
        {
            if(check2(ans - (1LL << bit)))
            {
                ans -= (1LL << bit);
            }
        }
    }

    cout << ans << endl;
}

int main()
{
    read();
    precomp();
    solve();
    
    return 0;
}

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