Submission #551613

#	Time	Username	Problem	Language	Result	Execution time	Memory
551613		hoanghq2004	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	90 ms	460 KiB

sculpture

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std;

int n, l, r;

namespace subtask1 {
    const int Nmax = 110;
    long long a[Nmax];
    int f[Nmax][Nmax];
    void solve() {
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
            a[i] += a[i - 1];
        }
        long long mask = 0;
        for (int _ = 40; _ >= 0; --_) {
            mask = mask << 1;
            memset(f, 0, sizeof(f));
            f[0][0] = 1;
            for (int i = 1; i <= n; ++i) {
                for (int j = 1; j <= r; ++j) {
                    for (int ii = 0; ii < i; ++ii) {
                        if ((mask | (a[i] - a[ii] >> _)) != mask) continue;
                        f[i][j] |= f[ii][j - 1];
                    }
                }
            }
            if (*max_element(f[n] + l, f[n] + r + 1) == 0) mask ^= 1;
        }
        cout << mask;
    }
}

namespace subtask2 {
    const int Nmax = 2010;
    long long a[Nmax];
    int f[Nmax];
    void solve() {
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
            a[i] += a[i - 1];
        }
        long long mask = 0;
        for (int _ = 40; _ >= 0; --_) {
            mask = mask << 1;
            memset(f, 60, sizeof(f));
            f[0] = 0;
            for (int i = 1; i <= n; ++i) {
                for (int ii = 0; ii < i; ++ii) {
                    if ((mask | (a[i] - a[ii] >> _)) != mask) continue;
                    f[i] = min(f[i], f[ii] + 1);
                }
            }
            if (f[n] > r) mask ^= 1;
        }
        cout << mask;
    }
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n >> l >> r;
    if (l == 1) subtask2 :: solve();
    else subtask1 :: solve();
}

Compilation message (stderr)

sculpture.cpp: In function 'void subtask1::solve()':
sculpture.cpp:26:43: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   26 |                         if ((mask | (a[i] - a[ii] >> _)) != mask) continue;
      |                                      ~~~~~^~~~~~~
sculpture.cpp: In function 'void subtask2::solve()':
sculpture.cpp:53:39: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   53 |                     if ((mask | (a[i] - a[ii] >> _)) != mask) continue;
      |                                  ~~~~~^~~~~~~

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