Submission #199211

#	Time	Username	Problem	Language	Result	Execution time	Memory
199211		Alexa2001	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	97 ms	504 KiB

sculpture

#include <bits/stdc++.h>

using namespace std;


typedef long long ll;
const int Nmax = 2005;


int dp[Nmax];
bitset<Nmax> can[Nmax];
int n, A, B;

ll s[Nmax];


bool check1(ll mask)
{
    int i, j;
    for(i=1; i<=n; ++i)
    {
        dp[i] = 1e9;
        for(j=0; j<i; ++j)
            if( ((s[i] - s[j]) | mask) == mask )
                dp[i] = min(dp[i], dp[j] + 1);
    }

    return dp[n] <= B;
}

bool check2(ll mask)
{
    int i, j, k;

    can[0][0] = 1;
    for(i=1; i<=n; ++i)
        {
            for(j=1; j<=B; ++j) can[i][j] = 0;

            for(k=0; k<i; ++k)
                if( ((s[i] - s[k]) | mask) == mask)
                    for(j=1; j<=B; ++j)
                        can[i][j] = can[i][j] | can[k][j-1];
        }

    for(i=A; i<=B; ++i)
        if(can[n][i]) return 1;
    return 0;
}

bool check(ll mask)
{
    if(A == 1) return check1(mask);
        else return check2(mask);
}

int main()
{
  //  freopen("input", "r", stdin);
    cin.sync_with_stdio(false); cin.tie(0);

    int i;
    cin >> n >> A >> B;
    for(i=1; i<=n; ++i) cin >> s[i], s[i] += s[i-1];

    for(i=0; (1LL<<i) <= s[n]; ++i); --i;

    ll ans = (1LL<<(i+1)) - 1;

    for(; i>=0; --i)
        if(check(ans ^ (1LL<<i)))
            ans ^= (1LL<<i);

    cout << ans << '\n';
    return 0;
}

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:66:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(i=0; (1LL<<i) <= s[n]; ++i); --i;
     ^~~
sculpture.cpp:66:38: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
     for(i=0; (1LL<<i) <= s[n]; ++i); --i;
                                      ^~

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