Submission #462196

#	Time	Username	Problem	Language	Result	Execution time	Memory
462196		prvocislo	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	113 ms	32012 KiB

sculpture

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
typedef long long ll;
using namespace std;

// 1-indexovanie!!!
const int maxn = 2005;
const ll logn = 41;
int n, a, b;
vector<ll> pf(maxn);
vector<vector<ll> > dp(maxn, vector<ll>(maxn, 0));
ll f(int l, int r) { return pf[r] - pf[l - 1]; }
bool check(ll mask) // existuje platne riesenie ak or tych suctov sa musi zmestit do tejto masky
{
    if (a == 1)
    {
        vector<int> d(n+1, maxn);
        queue<int> q; 
        q.push(0), d[0] = 0;
        while (!q.empty())
        {
            int i = q.front();
            q.pop();
            for (int j = i+1; j <= n; j++) if (d[j] == maxn && ((f(i+1, j)|mask) == mask))
                d[j] = d[i] + 1, q.push(j);
        }
        return d[n] <= b;
    }
    for (int i = 0; i <= n; i++) for (int j = 0; j <= n; j++) dp[i][j] = 0;
    dp[0][0] = 1;
    for (int i = 0; i < n; i++) for (int cnt = 0; cnt <= i; cnt++) if (dp[i][cnt])
        for (int j = i + 1; j <= n; j++) if ((f(i + 1, j) | mask) == mask)
            dp[j][cnt + 1] = 1;
    for (int cnt = a; cnt <= b; cnt++) if (dp[n][cnt]) return true;
    return false;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> a >> b;
    for (int i = 1; i <= n; i++) cin >> pf[i], pf[i] += pf[i - 1];
    ll mask = (1ll << logn) - 1;
    for (ll i = logn - 1; i >= 0; i--)
    {
        if (check(mask - (1ll << i))) mask -= (1ll << i);
    }
    cout << mask << "\n";
    return 0;
}

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