Submission #140734

#	Time	Username	Problem	Language	Result	Execution time	Memory
140734		BlueDiamond	Bali Sculptures (APIO15_sculpture)	C++14	0 / 100	2 ms	380 KiB

sculpture

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll N = 2000 + 7;
ll n, L, R;
ll a[N], b[N];
ll mi[N];

bool can(ll x)
{
        /// a | b | c | d <= x => a <= x, b <= x, c <= x, d <= x
        ll need = 0;
        ll i = 1;
        ll sau = 0;
        while (i <= n)
        {
                ll j = i;
                if (a[i] > x)
                        return 0;
                ll cur = a[i];
                while (j + 1 <= n && cur + a[j + 1] <= x)
                {
                        j++;
                        cur += a[j];
                }
                need++;
                i = j + 1;
                sau |= cur;
        }
        return (need <= R && sau <= x);
}

bool can_rev(ll x)
{
        /// a | b | c | d <= x => a <= x, b <= x, c <= x, d <= x
        ll need = 0;
        ll i = 1;
        ll sau = 0;
        while (i <= n)
        {
                ll j = i;
                if (b[i] > x)
                        return 0;
                ll cur = b[i];
                while (j + 1 <= n && cur + b[j + 1] <= x)
                {
                        j++;
                        cur += b[j];
                }
                need++;
                i = j + 1;
                sau |= cur;
        }
        return (need <= R && sau <= x);
}

signed main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(0), cout.tie(0);

        cin >> n >> L >> R;
        for (ll i = 1; i <= n; i++)
                cin >> a[i];
        for (ll i = 1; i <= n; i++)
                b[i] = a[n + 1 - i];

        if (L == 1)
        {
                ll lo = 0, hi = 0;
                for (ll i = 1; i <= n; i++)
                        hi += a[i];
                ll res = 0;
                while (lo <= hi)
                {
                        ll mid = (lo + hi) / 2;
                        if (can(mid) || can_rev(mid))
                        {
                                res = mid;
                                hi = mid - 1;
                        }
                        else
                                lo = mid + 1;
                }
                cout << res << "\n";
        }

        return 0;
}

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