Submission #164746

#	Time	Username	Problem	Language	Result	Execution time	Memory
164746		quocnguyen1012	Bali Sculptures (APIO15_sculpture)	C++14	50 / 100	328 ms	504 KiB

sculpture

#include <bits/stdc++.h>

#define Task "or"
#define pb push_back
#define int long long

using namespace std;
typedef long long ll;

mt19937 rng (chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 2005;

int testbit (ll x, int n){
    return x >> n & 1;
}

int N;
int a[maxn];
ll sum[maxn];
ll f[maxn];
int P, Q;

bool submask (ll mask1, ll mask2){
    return (mask1 & mask2) == mask1;
}

bool check (ll mask){
    for (int i=1; i<=N; ++i) f[i] = 1e9;
    for (int i=1; i<=N; ++i){
        for (int j=i-1; j>=0; --j){
            if (f[j] < 1e9 && submask (sum[i] - sum[j], mask)){
                f[i] = min(f[i], f[j] + 1);
            }
        }
    }
    //cerr << f[N];
    return f[N] <= Q;
}

signed main (void){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen (Task".in", "r")){
        freopen (Task".in", "r", stdin);
        freopen (Task".out", "w", stdout);
    }
    cin >> N >> P >> Q;
    for (int i=1; i<=N; ++i){
        cin >> a[i];
        sum[i] = sum[i-1] + a[i];
    }
    
    ll ans = (1ll << 62) - 1;
    for (int i=61; i>=0; --i){
        if (check (ans -(1ll << i)))
            ans -= (1ll << i);
        ///cerr << ans << '\n';
    }
    cout << ans;
}

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:44:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen (Task".in", "r", stdin);
         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:45:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen (Task".out", "w", stdout);
         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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