Submission #918341

#	Time	Username	Problem	Language	Result	Execution time	Memory
918341		phamducminh	Bali Sculptures (APIO15_sculpture)	C++17	0 / 100	1 ms	348 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 = 30;







///--------------------------------


void solve();

signed main(){









    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[200009], dp[109][109];

void solve(){


    long long ans=INF,n,L,R;

    cin >> n >> L >> R;


    for (long long i=0; i<n; i++){

        cin >> a[i];
    }


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



    for (long long i=0; i<=n+1; i++){
        for (long long j=0; j<=R+1; j++){
            dp[i][j]=INF;
        }
    }

    dp[0][0]=0;
    // dp[i][j][or]
    for (long long i=1; i<=n; i++){

        for (long long k=1; k<=R; k++){

            for (long long j=0; j<i; j++){

                long long sum=0;

                for (long long ii=j; ii<i; ii++){
                    sum+=a[ii];
                }

                // cout << sum << ' ' << j << ' ' << i << "\n";


                dp[i][k]=min(dp[i][k],dp[j][k-1]|sum);

            }
        }
    }

    for (long long i=L; i<=R; i++){
        ans=min(ans,dp[n][i]);

        // cout << dp[n][i] << "\n";
    }

    cout << ans;


}

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