Submission #994058

#TimeUsernameProblemLanguageResultExecution timeMemory
994058mispertionBali Sculptures (APIO15_sculpture)C++14
100 / 100
65 ms612 KiB
#include<bits/stdc++.h> using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); typedef long long ll; #define int ll typedef unsigned long long ull; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define pb push_back #define all(x) x.begin(), x.end() #define sz(x) (int)x.size() #define mispertion ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) #define F first #define S second #define getlast(s) (*s.rbegin()) #define debg cout << "OK\n" const ld PI = 3.1415926535; const int N = 2000+5; const int M = 7e6 + 1; int mod = 998244353; const int infi = INT_MAX; const ll infl = LLONG_MAX; const int P = 31; int mult(int a, int b) { return a * 1LL * b % mod; } int sum(int a, int b) { if (a + b < 0) return a + b + mod; if (a + b >= mod) return a + b - mod; return a + b; } ll binpow(ll a, ll n) { if (n == 0) return 1; if (n % 2 == 1) { return binpow(a, n - 1) * a % mod; } else { ll b = binpow(a, n / 2); return b * b % mod; } } int n, A, B, a[N], dp[N], pr[N], dp1[101][101]; bool check(int mask){ if(A == 1){ memset(dp, 0, sizeof dp); for(int i = 1; i <= n; i++) dp[i] = infi; dp[0] = 0; for(int i = 0; i < n; i++){ if(dp[i] == infi) continue; for(int nxt = i + 1; nxt <= n; nxt++){ if(((pr[nxt] - pr[i]) | mask) == mask) dp[nxt] = min(dp[nxt], dp[i] + 1); } } return (dp[n] <= B); } memset(dp1, 0, sizeof dp1); dp1[0][0] = 1; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ if(!dp1[i][j]) continue; for(int nxt = i + 1; nxt <= n; nxt++){ if(((pr[nxt] - pr[i]) | mask) == mask){ //cout << "()() " << nxt << ' ' << j + 1 << " )_)_) "; dp1[nxt][j + 1] = 1; } } } } int ans = 0; for(int gr = A; gr <= B; gr++){ ans |= dp1[n][gr]; } return ans; } void solve(){ cin >> n >> A >> B; for(int i = 1; i <= n; i++){ cin >> a[i]; pr[i] = pr[i - 1] + a[i]; } int ans = (1LL << 45) - 1; for(int i = 44; i >= 0; i--){ if(check(ans - (1LL << i))){ ans -= (1LL << i); } } cout << ans << '\n'; } signed main() { mispertion; int t = 1; //cin >> t; while(t--){ solve(); } return 0; }
#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...