Submission #953872

#TimeUsernameProblemLanguageResultExecution timeMemory
9538724QT0RBali Sculptures (APIO15_sculpture)C++17
100 / 100
48 ms600 KiB
#include <bits/stdc++.h> #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC target("avx2") using namespace std; #define ll long long bitset<2001> dp[2003]; ll sm[2003]; bitset<2001> mv[2003]; ll dp2[2003]; ll oo=1e18; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); ll n,a,b; cin >> n >> a >> b; for (ll i = 1; i<=n; i++){ cin >> sm[i]; sm[i]+=sm[i-1]; } ll ans=((ll)1<<41)-1; if (a!=1){ dp[0][0]=1; for (ll u = 40; u>=0; u--){ ll cur=ans-((ll)1<<u); for (ll i = 1; i<=n; i++){ for (ll j = 0; j<i; j++){ if ((cur|(sm[i]-sm[j]))==cur)mv[i][j]=1; else mv[i][j]=0; } for (ll j = i; j<=n; j++)mv[i][j]=0; } for (ll i = 1; i<=b; i++){ for (ll j = 1; j<=n; j++){ if ((dp[i-1]&mv[j]).any())dp[i][j]=1; else dp[i][j]=0; } } for (ll i = a; i<=b; i++){ if (dp[i][n]){ ans=cur; break; } } } } else{ for (ll u = 40; u>=0; u--){ ll cur=ans-((ll)1<<u); for (ll i = 1; i<=n; i++){ dp2[i]=oo; for (ll j = 0; j<i; j++){ if ((cur|(sm[i]-sm[j]))==cur)dp2[i]=min(dp2[i],1+dp2[j]); } } if (a<=dp2[n] && dp2[n]<=b){ ans=cur; } } } cout << ans << '\n'; }
#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...