Submission #1078701

#TimeUsernameProblemLanguageResultExecution timeMemory
1078701IcelastBali Sculptures (APIO15_sculpture)C++17
100 / 100
82 ms680 KiB
#include <iostream> #include <bits/stdc++.h> #define ll long long using namespace std; const ll maxn = 2005, INF = 4e18+9; bool dp[maxn][maxn]; void sub4(ll n, ll A, ll B, vector<ll> a){ 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; } ll f[maxn]; void sub5(ll n, ll A, ll B, vector<ll> a){ 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]; }; ll ans = (1LL<<51)-1; for(int it = 50; it >= 0; it--){ ans ^= (1LL<<it); for(int i = 1; i <= n; i++){ f[i] = INF; } f[0] = 0; for(int i = 1; i <= n; i++){ for(int k = 1; k <= i; k++){ if((ans|sum(k, i)) == ans){ f[i] = min(f[i], f[k-1]+1); } } } bool ok = false; if(f[n] <= B) ok = true; if(!ok){ ans ^= (1LL<<it); continue; } } cout << ans; } 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]; } if(n <= 100){ sub4(n, A, B, a); }else{ sub5(n, A, B, a); } } 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...