Submission #1104798

#TimeUsernameProblemLanguageResultExecution timeMemory
1104798SSSMBali Sculptures (APIO15_sculpture)C++14
100 / 100
107 ms4600 KiB
#include <bits/stdc++.h> /* #pragma GCC optimize ("O2") #pragma GCC optimize ("unroll-loops") #pragma GCC optimize ("Ofast") #pragma GCC target ("avx2") */ using namespace std; /* #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; */ #define F first #define S second #define pb push_back #define FIO freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout) #define md(a) (a%mod+mod)%mod #define all(a) a.begin(), a.end() #define MP make_pair #define lc id<<1 #define rc lc|1 #define mid (l+r)/2 #define kill(a) cout << a << "\n", exit(0) typedef pair<int,int> pii; typedef pair<long long ,long long> pll; typedef long long ll; typedef long double ld; typedef vector<vector<ll>> matrix; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); ll const maxn=2000+10, mod=1e9+7, INF=1e18, LOG=45, sq=65; ll poww(ll a, ll b, ll mod) { if (b == 0) return 1; return 1 * poww(1 * a * a % mod, b / 2, mod) * ((b % 2 == 1) ? a : 1) % mod; } ll n, a, b, A[maxn], ans=(1ll<<LOG)-1, dp[maxn]; bool dp2[maxn][maxn]; bool chk(ll mask) { for(ll i=0;i<=n;i++) { for(ll j=0;j<=n;j++) { dp2[i][j]=0; } } dp2[0][0]=1; dp[0]=0; for(ll i=1;i<=n;i++) { dp[i]=INF; ll s=0; for(ll j=i;j>=1;j--) { s+=A[j]; if((s&mask)!=s) continue; if(a==1) { dp[i]=min(dp[i], dp[j-1]+1); continue; } for(ll k=1;k<=i;k++) { dp2[i][k]|=dp2[j-1][k-1]; } } } if(a==1) return (dp[n]<=b); for(ll i=a;i<=b;i++) { if(dp2[n][i]) return 1; } return 0; } int main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>n>>a>>b; for(ll i=1;i<=n;i++) { cin>>A[i]; } for(ll i=LOG-1;i>=0;i--) { if(chk(ans^(1ll<<i))) ans^=(1ll<<i); } cout<<ans<<"\n"; 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...