Submission #69842

#	Time	Username	Problem	Language	Result	Execution time	Memory
69842		chpipis	Bali Sculptures (APIO15_sculpture)	C++11	100 / 100	143 ms	1428 KiB

sculpture

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define iter(v, i) for (__typeof__((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define fast_io_without_cstdio ios_base::sync_with_stdio(false), cin.tie(NULL)
#define all(v) (v).begin(), (v).end()
#define rep(i, s, e) for (int i = s; i < e; i++)

// START for segment tree
#define params int p, int L, int R
#define housekeep int mid = (L + R) >> 1, left = p << 1, right = left | 1
// END

#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc getchar
#define pc putchar
#endif

#if __cplusplus <= 199711L
template<class BidirIt>
BidirIt prev(BidirIt it, typename iterator_traits<BidirIt>::difference_type n = 1) {
    advance(it, -n);
    return it;
}

template<class ForwardIt>
ForwardIt next(ForwardIt it, typename iterator_traits<ForwardIt>::difference_type n = 1) {
    advance(it, n);
    return it;
}
#endif

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long double ldouble;

const double EPS = 1e-9;
const double PI = 3.141592653589793238462;

template<typename T>
inline T sq(T a) { return a * a; }

//#ifdef LOCAL_MACHINE
//#endif

const int LOGV = 45;
const int MAXN = 2005;
const int INF = 1e9;

int n, a, b;
int dp[MAXN];
bool can[MAXN][MAXN];
ll p[MAXN];

bool check(ll mask) {
    if (n <= 100) {
        can[0][0] = true;
        for (int k = 1; k <= b; k++) {
            for (int i = 0; i <= n; i++) {
                can[k][i] = false;
                if (i < k)
                    continue;
                for (int j = 0; j < i; j++)
                    if ((mask | (p[i] - p[j])) == mask && can[k - 1][j])
                        can[k][i] = true;
            }
            if (k >= a && can[k][n])
                return true;
        }
        return false;
    } else {
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            dp[i] = INF;
            for (int j = 0; j < i; j++)
                if ((mask | (p[i] - p[j])) == mask)
                    dp[i] = min(dp[i], dp[j] + 1);
        }
        return dp[n] >= a && dp[n] <= b;
    }
}

int main() {
    //freopen("", "r", stdin);
    //freopen("", "w", stdout);
    scanf("%d %d %d", &n, &a, &b);
    for (int i= 1; i <= n; i++) {
        int x; scanf("%d", &x);
        p[i] = p[i - 1] + x;
    }
    ll ans = (1LL << LOGV) - 1;
    for (int i = LOGV - 1; i >= 0; i--) {
        if (check(ans - (1LL << i)))
            ans -= 1LL << i;
    }
    printf("%lld\n", ans);
    return 0;
}

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:97:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &a, &b);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:99:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int x; scanf("%d", &x);
                ~~~~~^~~~~~~~~~

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