Submission #873742

#	Time	Username	Problem	Language	Result	Execution time	Memory
873742		thienhx	Bali Sculptures (APIO15_sculpture)	C++17	37 / 100	26 ms	600 KiB

sculpture

#include <bits/stdc++.h>
using namespace std;

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")

using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using str = string;
using ld = long double;
using db = double;

///--------------------------------

#define           F   first
#define           S   second
#define          pb   push_back
#define          lb   lower_bound
#define          ub   upper_bound
#define       sz(x)   (int)((x).size())
#define      all(x)   (x).begin(), (x).end()
#define     rall(x)   (x).rbegin(), (x).rend()
#define   mem(f, x)   memset(f, x, sizeof(f))
#define  uniqueV(x)   sort(all(x)), (x).resize(unique(all(x)) - x.begin())

template<class T> bool maximize(T &a, const T &b){ return (a < b ? a = b, 1 : 0); }
template<class T> bool minimize(T &a, const T &b){ return (a > b ? a = b, 1 : 0); }

///--------------------------------

#define PROBLEM "test"

const int MOD = 1e9 + 7; // 998244353;
const ll INF = 1e18;
const ld eps = 1e-9;
const ld PI = acos(-1);
const int dx[4]{0, 1, 0, -1}, dy[4]{1, 0, -1, 0}; // R D L U
const int ddx[4]{-1, 1, 1, -1}, ddy[4]{1, 1, -1, -1}; // UR DR DL UL

///--------------------------------

void precalc();
void solve();

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    if (fopen(PROBLEM".inp", "r")) {
        freopen(PROBLEM".inp", "r", stdin);
        freopen(PROBLEM".out", "w", stdout);
    }

    constexpr bool MULTI_TEST = 0;

    int t = 1;
    if (MULTI_TEST) cin >> t;

    while (t--)
        solve();
    
    // cerr << setprecision(3) << fixed;
    // cerr << "[" << 1.0 * clock() / CLOCKS_PER_SEC << "s]  ";
}

///--------------------[PROBLEM SOLUTION]--------------------///

const int LOG = 40;
const int maxn = 2020;
bool dp[107][107];
ll v[maxn], dp2[maxn];

bool match(ll mask, ll suf, ll p) {
    return (((mask >> p << p) | suf) == suf);
}

void solve() {
    ll n, A, B;
    cin >> n >> A >> B;

    for (int i = 1; i <= n; i++)
        cin >> v[i];

    if (n <= 100) {
        ll suf = 0;
        for (int j = LOG; j >= 0; j--) {
            mem(dp, false);
            dp[0][0] = true;

            for (int i = 1; i <= n; i++) {
                for (int k = 1; k <= i; k++) {
                    ll sum = 0;
                    for (int h = i; h >= 1; h--) {
                        sum += v[h];

                        if (match(sum, suf, j))
                            dp[i][k] |= dp[h - 1][k - 1];
                    }
                }
            }

            bool check = false;
            for (int i = A; i <= B; i++)
                if (dp[n][i])
                    check = true;

            if (!check) 
                suf += (1 << j);
        }

        cout << suf << '\n';
    }   
    else {

    } 
}

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:52:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         freopen(PROBLEM".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:53:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         freopen(PROBLEM".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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