Submission #317750

#TimeUsernameProblemLanguageResultExecution timeMemory
317750soroushBali Sculptures (APIO15_sculpture)C++14
100 / 100
244 ms6272 KiB
/* #pragma GCC optimize("O2") #pragma GCC optimize("unroll-loops") #pragma GCC target("avx,avx2,sse,sse2,fma,tune=native") //*/ #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int ,int > pii; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const ll maxn = 2100; const ll mod =1e9+7; const ld PI = acos((ld)-1); #define int ll #define pb push_back #define endl '\n' #define dokme(x) cout << x , exit(0) #define migmig ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define ms(x , y) memset(x , y , sizeof x) ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);} int n; int a[maxn]; int l , r; void sub1(){ ll ans = 1e18; for(int i = 0 ; i < (1 << (n - 1)) ; i ++) if(__builtin_popcount(i)+1 >= l and __builtin_popcount(i)+1 <= r){ vector < ll > vec; vec.clear(); vec.pb(0); for(int j = 0 ; j < n ; j ++){ vec.back()+=a[j]; if(i & (1 << j)) vec.pb(0); } ll orr = 0; for(auto x : vec) orr|=x; ans = min(ans , orr); } dokme(ans); } int mark[200][200][600]; bool m[200][200]; int ans; void dfs(int i , int k , int Or){ if(i == n and k >= l and k <= r) ans = min(ans , Or); mark[i][k][Or] = 1; int sum = 0; for(int j = i+1 ; j <= n ; j ++){ sum += a[j - 1]; if(!mark[j][k+1][Or|sum]) dfs(j, k + 1 , Or | sum); } } void sub2(){ ans = 1e9; dfs(0 , 0 , 0); dokme(ans); } ll dp[maxn]; ll solve(){ ans = (1LL << 60LL)-1; for(int i = 59 ; i >= 0 ; i --){ ms(dp , 63), dp[0] = 0; ans ^= (1LL << i); for(int j = 0 ; j < n ; j ++){ ll sum = 0; for(int k = j ; k < n ; k ++) sum += a[k], dp[k+1] = min(dp[k+1] ,(ans - (sum|ans))?dp[k+1] : dp[j]+1); } if(dp[n] > r) ans += (1LL << i); } return(ans); } ll sub4(){ ans = (1LL << 60LL)-1; for(int i = 59 ; i >= 0 ; i --){ ans ^= (1LL << i); ms(m , 0); m[0][0] = 1; for(int i = 0 ; i < n ; i ++) for(int j = 0 ; j < r ; j ++ ){ ll sum = 0; for(int k = i ; k < n ; k ++) sum += a[k] , m[k+1][j+1] |= (m[i][j] && !((ans - (sum|ans)))); } bool ok = 0; for(int i = l ; i <= r ; i ++) ok|=m[n][i]; if(!ok)ans+=(1LL << i); } return(ans); } int32_t main(){ migmig; cin >> n >> l >> r; for(int i = 0 ; i < n ; i ++) cin >> a[i]; if(n <= 20){ sub1(); } if(n <= 50 and r <= 20 and *max_element(a , a + n) <= 10){ sub2(); } if(l == 1){ dokme(solve()); } //sub4 cout << sub4(); 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...