oj.uz

Submission #140734

# Submission time Handle Problem Language Result Execution time Memory
140734 2019-08-04T19:12:46 Z BlueDiamond Bali Sculptures (APIO15_sculpture) C++14
0 / 100
 2 ms 380 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Incorrect 2 ms 376 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Incorrect 2 ms 376 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Incorrect 2 ms 376 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Incorrect 2 ms 376 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Incorrect 2 ms 376 KB Output isn't correct
7 Halted 0 ms 0 KB -