Submission #249016

#	Time	Username	Problem	Language	Result	Execution time	Memory
249016		SamAnd	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	187 ms	504 KiB

sculpture

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N4 = 102, N5 = 2002, INF = 1000006;

int n, ul, ur;
int a[N5];

void ka()
{
    scanf("%d%d%d", &n, &ul, &ur);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
}

void solv4()
{
    bool dp[N4][N4];
    ll ans = 0;
    for (int i = 50; i >= 0; --i)
    {
        memset(dp, false, sizeof dp);
        dp[0][0] = true;
        for (int j = 1; j <= n; ++j)
        {
            ll s = 0;
            for (int k = j; k >= 1; --k)
            {
                s += a[k];
                if (((ans >> i) & (s >> i)) != (s >> i))
                    continue;
                for (int q = 0; q <= n; ++q)
                {
                    if (dp[k - 1][q])
                        dp[j][q + 1] = true;
                }
            }
        }
        bool z = false;
        for (int q = ul; q <= ur; ++q)
        {
            if (dp[n][q])
            {
                z = true;
                break;
            }
        }
        if (!z)
        {
            ans |= (1LL << i);
        }
    }
    printf("%lld\n", ans);
}

void solv5()
{
    int dp[N5];
    ll ans = 0;
    for (int i = 50; i >= 0; --i)
    {
        for (int j = 1; j <= n; ++j)
        {
            dp[j] = INF;
            ll s = 0;
            for (int k = j; k >= 1; --k)
            {
                s += a[k];
                if (((ans >> i) & (s >> i)) != (s >> i))
                    continue;
                dp[j] = min(dp[j], dp[k - 1] + 1);
            }
        }
        if (dp[n] > ur)
        {
            ans |= (1LL << i);
        }
    }
    printf("%lld\n", ans);
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    ka();
    if (ul == 1)
        solv5();
    else
        solv4();
    return 0;
}

//while ((double)clock() / CLOCKS_PER_SEC <= 0.9){}

Compilation message (stderr)

sculpture.cpp: In function 'void ka()':
sculpture.cpp:18:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &ul, &ur);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:20:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
         ~~~~~^~~~~~~~~~~~~

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