Submission #744189

#	Time	Username	Problem	Language	Result	Execution time	Memory
744189		fanwen	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	61 ms	768 KiB

sculpture

#include <bits/stdc++.h>

using namespace std;

#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()

#define REP(i, n) for (int i = 0, _n = n; i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define FORE(it, s) for (__typeof(s.begin()) it = (s).begin(); it != (s).end(); ++it)

#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define file(TASK)                         \
    if (fopen(TASK ".inp", "r")) {         \
        freopen(TASK ".inp", "r", stdin);  \
        freopen(TASK ".out", "w", stdout); \
    }

template <class U, class V> bool maximize(U &A, const V &B) { return (A < B) ? (A = B, true) : false; }
template <class U, class V> bool minimize(U &A, const V &B) { return (A > B) ? (A = B, true) : false; }

const int MAXN = 2e3 + 5;

int N, L, R, dp[MAXN][MAXN];
long long a[MAXN];

namespace sub1 {

    void Main() {
        long long ans = 0;
        FORD(bit, 40, 0) {
            long long mask = ans + MASK(bit) - 1;
            FOR(i, 0, N) FOR(x, 0, R) dp[i][x] = 0;
            dp[0][0] = 1;
            FOR(i, 1, N) FOR(j, 1, R) FOR(k, 1, i) {
                long long sum = a[i] - a[k - 1];
                if((sum & mask) == sum) dp[i][j] |= dp[k - 1][j - 1];
            }
            bool check = 0;
            FOR(i, L, R) check |= dp[N][i];
            if(check == 0) ans |= MASK(bit);
        }
        cout << ans;
        exit(0);
    }
}


namespace sub2 {

    void Main() {

        long long ans = 0;
        vector <int> F(N + 1);
        FORD(bit, 40, 0) {
            long long mask = ans + MASK(bit) - 1;
            fill(ALL(F), N + 1);
            F[0] = 0;
            FOR(i, 1, N) FOR(j, 1, i) {
                long long sum = a[i] - a[j - 1];
                if((sum & mask) == sum) minimize(F[i], F[j - 1] + 1);
            }
            if(F[N] > R) ans |= MASK(bit);
        }

        cout << ans; exit(0);
    }
}
void process(void) {

    cin >> N >> L >> R;

    FOR(i, 1, N) cin >> a[i], a[i] += a[i - 1];

    if(N <= 100) sub1::Main();
    sub2::Main();
}
signed main() {
    file("TASK");
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int test = 1;
    // cin >> test;
    while(test--) {
        process();
        cout << '\n';
    }
    cerr << "Time elapsed: " << TIME << " s.\n";
    return (0 ^ 0);
}

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:17:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         freopen(TASK ".inp", "r", stdin);  \
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:81:5: note: in expansion of macro 'file'
   81 |     file("TASK");
      |     ^~~~
sculpture.cpp:18:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         freopen(TASK ".out", "w", stdout); \
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:81:5: note: in expansion of macro 'file'
   81 |     file("TASK");
      |     ^~~~

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