Submission #1078681

#TimeUsernameProblemLanguageResultExecution timeMemory
1078681IcelastBali Sculptures (APIO15_sculpture)C++17
71 / 100
19 ms868 KiB
#include <iostream> #include <bits/stdc++.h> #define ll long long using namespace std; const ll maxn = 105, INF = 4e18+9; bool dp[maxn][maxn]; void solve(){ ll n, A, B; cin >> n >> A >> B; vector<ll> a(n+1); for(int i = 1; i <= n; i++){ cin >> a[i]; } vector<ll> pf(n+1, 0); for(int i = 1; i <= n; i++) pf[i] = pf[i-1]+a[i]; auto sum = [&](int i, int j) -> ll{ return pf[j]-pf[i-1]; }; vector<bool> possible_j(n+1, 1); ll ans = (1LL<<51)-1; for(int it = 50; it >= 0; it--){ ans ^= (1LL<<it); for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ dp[i][j] = 0; } } dp[0][0] = 1; for(int i = 1; i <= n; i++){ for(int j = 1; j <= i; j++){ bool trs = 0; for(int k = 1; k <= i; k++){ if((ans|sum(k, i)) == ans){ trs |= dp[k-1][j-1]; } } dp[i][j] = trs; } } bool ok = false; for(int j = A; j <= B; j++){ if(dp[n][j]&&possible_j[j]){ ok = true; } } if(!ok){ ans ^= (1LL<<it); continue; } for(int j = A; j <= B; j++){ if(dp[n][j]&&possible_j[j]){ possible_j[j] = 1; }else{ possible_j[j] = 0; } } } cout << ans; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); solve(); }
#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...