//******************/
//* I<3 C++ */
//* I WANT ANY AC */
//* I LOVE PROGRAM!*/
//*IT'S long longERESTING*/
//* I LOVE PROGRAM!*/
//* IN CONTESTS */
//* GET SCORE */
//* AC CODE */
//* LET'S */
//* GO */
//* Written by: */
//* Duc Minh */
#include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <algorithm>
#include <string>
#include <queue>
#include <cctype>
#include <cstring>
#include <iomanip>
#include <deque>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
using namespace std;
// using namespace __gnu_pbds;
#define file(name) freopen(name".inp", "r", stdin);\
freopen(name".out", "w", stdout);
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define all(a) a.begin(),a.end()
#define endl "\n"
#define all1(a) a+1,a+n+1
#define unordered_map map
#define Accepted 0
// #define push_back emplace_back
// #define gcd(a,b) __gcd(a,b);
// #define lcm(a,b) (a*b)/gcd(a,b);
const long long INF = (long long)1e18;
const long long MOD = (long long)1e9+7;
const long long MODD = 14062008; /// 998244353
const long long maxN = 2e5+9;
const long long LOG = 57;
///--------------------------------
void solve();
signed main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#ifndef ONLINE_JUDGE
file("ducminh");
#endif
// file("tbrackets");
long long t;
// cin >> t;
t=1;
while (t--){
solve();
}
cerr << "Time elapsed: " << TIME << "s.\n";
cerr << "ducminh" << "\n";
return Accepted;
}
///--------------------[PROBLEM SOLUTION]--------------------///
long long a[2009], dp[2009][2009], pre[2009];
long long ans=INF,n,L,R;
void sub1(){
for (long long mask=0; mask<(1<<n); mask++){
long long sum=0,g=0;
for (long long i=0; i<n; i++){
sum+=a[i];
if ((mask>>i)&1){
g|=sum;
sum=0;
}
}
g|=sum;
long long bits=__builtin_popcount(mask) + ((mask & (1 << (n - 1))) == 0);
if (L<=bits && bits<=R) ans=min(ans,g);
}
cout << ans;
exit(0);
}
void sub2(){
long long dp[59][29][509];
memset(dp, false ,sizeof dp);
dp[0][0][0] = true;
const int N=500;
for (int i=1; i<=n; i++){
pre[i]=pre[i-1]+a[i-1];
}
for (long long i=0; i<n; i++){
for (long long k=0; k<=min(i,R-1); k++){
for (long long j=0; j<=N; j++){
if (!dp[i][k][j]) continue;
for (long long t=i+1; t<=n; t++){
dp[t][k+1][j|(pre[t]-pre[i])] |= dp[i][k][j];
}
}
}
}
for (long long j = L ; j <= R ; j++)
for (long long t = 0; t <= N; t++){
if (dp[n][j][t]) ans=min(ans,t);
}
cout << ans;
exit(0);
}
void sub3(){
const int N=2000;
for (long long i=0; i<=n+1; i++){
// pre[i]=0;
for (long long j=0; j<=N+1; j++){
dp[i][j]=INF;
}
}
// sort(a,a+n);
// for (int i=1; i<=n; i++){
// pre[i]=pre[i-1]+a[i];
// // cout << pre[i] << ' ';
// }
dp[0][0]=0;
// dp[i][j][or]
for (long long i=0; i<n; i++){
for (int k=0; k<=N; k++){
for (int j=i; j<n; j++){
dp[j+1][k|(pre[j]-pre[i-1])]=min(dp[j+1][k|(pre[j]-pre[i-1])],dp[i][k]+1);
// cout << i << ' ' << j << ' ' << dp[i][k] << "\n";
}
}
}
for (int k=0; k<=N; k++){
// cout << dp[n-1][k] << ' ';
if (dp[n][k]<=R) {cout << k; exit(0);}
}
// cout << dp[n][5];
// exit(0);
}
bool checksub4(){
long long dp[2009][2009];
memset(dp, false ,sizeof dp);
dp[0][0] = true;
const int N=500;
// for (int i=1; i<=n; i++){
// pre[i]=pre[i-1]+a[i-1];
// }
for (long long i=0; i<n; i++){
for (long long k=0; k<=min(i,R-1); k++){
// if (!dp[i][k]) continue;
long long sum=0;
for (long long t=i; t<=n; t++){
sum+=a[t];
if ((sum|ans)==ans) dp[t+1][k+1] |= dp[i][k];
}
}
}
for (long long j = L ; j <= R ; j++)
if (dp[n][j]) return true;
return false;
exit(0);
}
void sub4(){
ans = (1LL<<LOG) - 1;
for (long long i=LOG-1; i>=0; i--){
ans^=1LL<<i;
if (!checksub4()){
ans|=1LL<<i;
}
}
cout << ans;
exit(0);
}
bool checksub5(){
long long dp[20009];
for (int i = 0; i <= n; i++) {
dp[i] = 100000;
}
dp[0] = 0;
const int N=500;
// for (int i=1; i<=n; i++){
// pre[i]=pre[i-1]+a[i-1];
// }
for (long long i=0; i<n; i++){
if (dp[i]>=100000) continue;
// if (!dp[i][k]) continue;
long long sum=0;
for (long long t=i; t<n; t++){
sum+=a[t];
if ((sum|ans)==ans) dp[t+1] = min(dp[t+1],dp[i]+1);
}
}
return dp[n]<=R;
exit(0);
}
void sub5(){
ans = (1LL<<LOG) - 1;
for (long long i=LOG-1; i>=0; i--){
ans^=1LL<<i;
if (!checksub5()){
ans|=1LL<<i;
}
}
cout << ans;
exit(0);
}
void solve(){
cin >> n >> L >> R;
long long mx=-1e9;
for (long long i=0; i<n; i++){
cin >> a[i]; if (i==0) pre[i]=a[i]; else pre[i]=pre[i-1]+a[i];
mx=max(mx,a[i]);
}
// cout << pre[2]-pre[0] << "\n";
if (n<=20) sub1();
if (n<=50 && R<=min(20LL,n)) sub2();
if (n<=100 && L==1 && mx<=3000) sub3();
if (n<=100 && mx<=1000000000) sub4();
sub5();
}
Compilation message
sculpture.cpp: In function 'bool checksub4()':
sculpture.cpp:252:15: warning: unused variable 'N' [-Wunused-variable]
252 | const int N=500;
| ^
sculpture.cpp: In function 'bool checksub5()':
sculpture.cpp:325:15: warning: unused variable 'N' [-Wunused-variable]
325 | const int N=500;
| ^
sculpture.cpp: In function 'int main()':
sculpture.cpp:40:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
40 | #define file(name) freopen(name".inp", "r", stdin);\
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:74:9: note: in expansion of macro 'file'
74 | file("ducminh");
| ^~~~
sculpture.cpp:41:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
41 | freopen(name".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:74:9: note: in expansion of macro 'file'
74 | file("ducminh");
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
