Submission #1115606

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115606		gdragon	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	346 ms	592 KiB

sculpture

#include <bits/stdc++.h>
using namespace std;
#define TASK "long"
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define GETBIT(mask, i) ((mask) >> (i) & 1)
#define MASK(i) ((1LL) << (i))
#define SZ(x) ((int)(x).size())
#define mp make_pair
#define CNTBIT(mask) __builtin_popcount(mask)
template<class X, class Y> bool maximize(X &x, Y y){ if (x < y) {x = y; return true;} return false;};
template<class X, class Y> bool minimize(X &x, Y y){ if (x > y) {x = y; return true;} return false;};
typedef pair<int, int> ii;
const int N = 1e5 + 5;
const long long INF = (long long)1e18 + 7;
const int mod = 1e9 + 7;
int n, A, B;
vector<long long> f;
long long a[N];
void read() {
    cin >> n >> A >> B;
    f.assign(n + 1, 0);
    for(int i = 1; i <= n; i++) {
        cin >> f[i];
        a[i] = f[i];
        f[i] += f[i - 1];
    }
}
long long sum(int l, int r) {
    return f[r] - f[l - 1];
}
void sub1() {
    int m = n - 1;
    long long ans = INF;
    for(int mask = 0; mask < MASK(m); mask++) {
        if (CNTBIT(mask) + 1 > B || CNTBIT(mask) + 1 < A) continue;
        int pre = 1;
        long long res = 0;
        for(int i = 1; i < n; i++) if (GETBIT(mask, i - 1)) {
            res |= sum(pre, i);
            pre = i + 1;
        }
        res |= sum(pre, n);
        ans = min(ans, res);
    }
    cout << ans;
}
void sub3() {
    vector<vector<vector<long long>>> dp(n + 2, vector<vector<long long>>(B + 2));
    dp[0][0].push_back(0);
    for(int i = 1; i <= n; i++) {
        for(int k = 1; k <= min(i, B); k++) {
            long long x = 0;
            for(int j = i; j >= 1; j--) {
                x += a[j];
                long long mn1 = INF, mn2 = INF, mn3 = INF;
                for(long long z: dp[j - 1][k - 1]) {
                    long long tmp = (x | z);
                    if (mn1 > tmp) {
                        mn3 = mn2;
                        mn2 = mn1;
                        mn1 = tmp;
                    }
                    else if (mn2 > tmp) {
                        mn3 = mn2;
                        mn2 = tmp;
                    }
                    else minimize(mn3, tmp);
                }
                if (mn1 != INF) dp[i][k].push_back(mn1);
                if (mn2 != INF) dp[i][k].push_back(mn2);
                if (mn3 != INF) dp[i][k].push_back(mn3);
            }
        }
    }
    long long ans = INF;
    for(int k = A; k <= B; k++) {
        for(long long x: dp[n][k]) ans = min(ans, x);
    }
    cout << ans;
}
const int NUMBIT = 41;
bool compare(long long mask1, long long mask2, int x) {
    for(int i = NUMBIT; i >= x; i--) if (!GETBIT(mask1, i)) {
        if (GETBIT(mask2, i)) return false;
    }
    return true;
}
bool setZero1(long long cur, int bit) {
    const pair<long long, long long> inf = mp(INF, INF);
    vector<pair<long long, long long>> dp(n + 2, inf);
    // dp[0][0] = {0, 0};
    dp[0] = {0, 0}; // (group, sumOr)
    for(int i = 1; i <= n; i++) {
        long long val = 0;
        for(int j = i; j >= 1; j--) {
            val += a[j];
            if (dp[j - 1] == inf) continue;
            if (compare(cur, (dp[j - 1].se | val), bit)) {
                minimize(dp[i], mp(dp[j - 1].fi + 1, dp[j - 1].se | val));
            }
        }
    }
    if (dp[n] == inf) return false;
    if (dp[n].fi < A || dp[n].fi > B) return false;
    return true;
}
bool setZero0(long long cur, int bit) {
    vector<vector<long long>> dp(n + 2, vector<long long>(B + 2, INF));
    dp[0][0] = 0; 
    for(int i = 1; i <= n; i++) {
        for(int k = 1; k <= min(i, B); k++) {
            long long val = 0;
            for(int j = i; j >= 1; j--) {
                val += a[j];
                if (dp[j - 1][k - 1] == INF) continue;
                if (compare(cur, (dp[j - 1][k - 1] | val), bit)) {
                    minimize(dp[i][k], dp[j - 1][k - 1] | val);
                }
            }
        }
    }
    for(int k = A; k <= B; k++) if (dp[n][k] < INF) return true;
    return false;
}
void sub4() {
    long long cur = 0;
    for(int i = 0; i <= NUMBIT; i++) cur |= MASK(i);
    for(int i = NUMBIT; i >= 0; i--) {
        cur ^= MASK(i);
        if (A > 1) {
            if (!setZero0(cur, i)) cur |= MASK(i);  
        }
        else {
            if (!setZero1(cur, i)) cur |= MASK(i);
        }
    }
    cout << cur << endl;
}
void solve() {
    sub4(); return;
    if (n <= 20) {
        sub1();
        return;
    }
    else {
        sub3();
    }
}
signed 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);
    }
    // cerr << (1082353817592 | 53288572918018395) << endl;
    int test = 1;
    // cin >> test;
    while(test--) {
        read();
        solve();
    }
    return 0;
}

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:156:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  156 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:157:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  157 |         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