Submission #918528

#	Time	Username	Problem	Language	Result	Execution time	Memory
918528		phamducminh	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	223 ms	32080 KiB

sculpture

//******************/
//*   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);


    // 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 (stderr)

sculpture.cpp: In function 'bool checksub4()':
sculpture.cpp:250:15: warning: unused variable 'N' [-Wunused-variable]
  250 |     const int N=500;
      |               ^
sculpture.cpp: In function 'bool checksub5()':
sculpture.cpp:323:15: warning: unused variable 'N' [-Wunused-variable]
  323 |     const int N=500;
      |               ^

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 21 / 21
• Subtask 4: 25 / 25
• Subtask 5: 29 / 29