Submission #623688

#	Time	Username	Problem	Language	Result	Execution time	Memory
623688		lmqzzz	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	66 ms	384 KiB

sculpture

#include<bits/stdc++.h>
using namespace std;
#define           fi    first
#define           se    second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    v.resize(unique(all(v)) - v.begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int32_t)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define         left    Kurumi_Tokisaki
#define        right    Kei_Karuizawa
#define         next    Mai_Sakurajima
#define          div    Yume_Irido
#define         prev    Chizuru_Mizuhara
#define    cntbit(x)    __builtin_popcountll(x)
#define      MASK(x)    ( 1ll << (x) )
#define          Yes    cout << "Yes"
#define          YES    cout << "YES"
#define           No    cout << "No"
#define           NO    cout << "NO"
#define           AA    cout << "Alice"
#define           BB    cout << "Bob"

#ifdef LMQZZZ
#include "lmqzzz.h"
#else
#define deb(x...) 3326
#endif

/// TASK
/// -----------------------------
#define TASK "C"
///------------------------------

void solve();
void init();

void gentest() {
        if (fopen(TASK ".inp", "r"))
                freopen(TASK ".inp","w",stdout);
        srand(time(0));
        exit(0);
}
int32_t main() {
        ios_base::sync_with_stdio(0);
        cin.tie(0);      cout.tie(0);
        if (fopen(TASK ".inp", "r")) {
                freopen(TASK ".inp", "r", stdin);
                freopen(TASK ".out", "w", stdout);
        }
//        gentest();
        /// =================================
                constexpr bool MULTITEST = 0;
        /// ================================
        init();
        int32_t TT = 1;
        if ( MULTITEST ) cin >> TT;
        for(int32_t TTT = 1; TTT <= TT; TTT ++) {
                solve();
//                cout << '\n';
        }
}

template <class T> inline T min(const T &a, const T &b, const T &c) { return min(a, min(b, c)); }
template <class T> inline T max(const T &a, const T &b, const T &c) { return max(a, max(b, c)); }
template <class T, class U> inline bool mini(T &a, const U &b) { if (a > b) { a = b; return 1; } return 0; }
template <class T, class U> inline bool maxi(T &a, const U &b) { if (a < b) { a = b; return 1; } return 0; }

constexpr     int16_t dr[]  =  {0, 0, -1, 1};
constexpr     int16_t dc[]  =  {1, -1, 0, 0};
constexpr      int64_t MOD  =  998244353 ;
constexpr     int32_t MAXN  =  1e2 + 10;



void init() {}

int n, a, b;
int64_t w[2020];
int f[MAXN][MAXN];
int g[2020];

void solve() {
        cin >> n >> a >> b;
        for (int i = 1; i <= n; i ++) {
                cin >> w[i];
                w[i] += w[i - 1];
        }
        if (a != 1) {
                int64_t minMask = MASK(42) - 1;
                for (int bit = 41; bit >= 0; bit --) {
                        minMask ^= MASK(bit);
                        mem(f, 0);
                        f[0][0] = 1;
                        for (int i = 0; i < n; i ++) {
                                for (int j = 0; j <= i; j ++) {
                                        if (f[i][j]) {
                                                for (int k = i + 1; k <= n; k ++) {
                                                        if (((w[k] - w[i]) | minMask) == minMask) {
                                                                f[k][j + 1] = 1;
                                                        }
                                                }
                                        }
                                }
                        }
                        bool ok = 0;
                        for (int i = a; i <= b; i ++) {
                                ok |= f[n][i];
                        }
                        if (ok == 0) {
                                minMask ^= MASK(bit);
                        }
                }
                cout << minMask;
        } else {
                int64_t minMask = MASK(42) - 1;
                for (int bit = 41; bit >= 0; bit --) {
                        minMask ^= MASK(bit);
                        mem(g, 0x3f);
                        g[0] = 0;
                        for (int i = 0; i < n; i ++) {
                                if (g[i] < b) {
                                        for (int j = i + 1; j <= n; j ++) {
                                                if (((w[j] - w[i]) | minMask) == minMask) {
                                                        g[j] = min(g[i] + 1, g[j]);
                                                }
                                        }
                                }
                        }

                        if (g[n] > b) {
                                minMask ^= MASK(bit);
                        }
                }
                cout << minMask;
        }
}

Compilation message (stderr)

sculpture.cpp: In function 'void gentest()':
sculpture.cpp:48:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |                 freopen(TASK ".inp","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp: In function 'int32_t main()':
sculpture.cpp:56:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |                 freopen(TASK ".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:57:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |                 freopen(TASK ".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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