Submission #241849

#TimeUsernameProblemLanguageResultExecution timeMemory
241849syyBali Sculptures (APIO15_sculpture)C++17
100 / 100
115 ms4352 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; #define FOR(i, a, b) for(ll i = (ll)a; i <= (ll)b; i++) #define DEC(i, a, b) for(ll i = (ll)a; i >= (ll)b; i--) typedef pair<ll, ll> pi; typedef pair<ll, pi> pii; typedef pair<pi, pi> pipi; #define f first #define s second typedef vector<ll> vi; typedef vector<pi> vpi; typedef vector<pii> vpii; #define pb push_back #define pf push_front #define all(v) v.begin(), v.end() #define disc(v) sort(all(v)); v.resize(unique(all(v)) - v.begin()); #define INF (ll) 1e9 + 100 #define LLINF (ll) 1e18 #define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) ll n, a, b, arr[2005], ans; bool ok() { //a = 1 ll dp[2005]; FOR(i, 1, n+1) dp[i] = LLINF; dp[1] = 0; FOR(i, 1, n) { ll sum = 0; FOR(j, i, n) { sum += arr[j]; if ((sum | ans) == ans) dp[j+1] = min(dp[j+1], dp[i] + 1); } } return dp[n+1] <= b; } bool ok2() { // a != 1 bool dp[2005][2005]; memset(dp, 0, sizeof dp); dp[1][0] = 1; FOR(i, 1, n) FOR(j, 0, b-1) { ll sum = 0; FOR(k, i, n) { sum += arr[k]; if ((sum | ans) == ans) dp[k+1][j+1] |= dp[i][j]; } } FOR(i, a, b) if (dp[n+1][i]) return true; return false; } int main() { fastio; cin >> n >> a >> b; FOR(i, 1, n) cin >> arr[i]; ans = (1ll<<42)-1; DEC(i, 41, 0) { ans ^= (1ll<<i); if (!(a == 1 ? ok() : ok2())) ans ^= (1ll<<i); } cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...