Submission #492750

#	Time	Username	Problem	Language	Result	Execution time	Memory
492750		5AP	Bali Sculptures (APIO15_sculpture)	C++17	37 / 100	2 ms	736 KiB

sculpture

#include<iostream>
#include<vector>
#include<map>
#include<math.h>
#include<set>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<queue>
#include<bitset>
 
using namespace std;
 
#pragma GCC optimize ("Ofast")

#define all(x) x.begin() , x.end()
#define MP(x , y) make_pair(x , y)
#define wall cerr<<"--------------------------------------"<<endl
#define PB(x) push_back(x)

typedef long long int ll;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef pair<ll , ll> pll;
typedef pair<int , int> pii;
typedef long double db;
typedef pair<pll , ll> plll;
typedef pair<int , pii> piii;
typedef pair<pll , pll> pllll;
 
const ll maxn = 2e3+5 , maxc = 1e2+5, md = 1e9 + 7 , inf = 2e16;

ll n , a , b , x[maxn] , pre[maxn] , ans=(1ll<<34)-1;
vl dp1;

bool sol1(ll mask){
    dp1.assign(n+1 , n+1);
    dp1[0]=0;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < i; j++)
            if((mask|(pre[i]-pre[j])) == mask) dp1[i]=min(dp1[i] , dp1[j]+1);
    return dp1[n]<=b;
}

bool sol2(ll mask){
    bitset<maxn> dp2[maxn];
    dp2[0][0]=1;
    for (int i = 1; i <= n; i++)
        for(int use = 1 ; use<=i ; use++)
            for(int j = 0 ; j<i ; j++)
                if(((mask|(pre[i]-pre[j]))==mask)&&dp2[j][use-1]) dp2[i][use]=1;
    for(int use =a ; use<=b ; use++) if(dp2[n][use])return true;
    return false;
}

void solve()
{
    cin>>n>>a>>b;
    pre[0]=0;
    for(int i = 1 ; i<=n ; i++)cin>>x[i] , pre[i]=pre[i-1]+x[i];
    for(int w = 33 ; w>=0 ; w--)
    {
        if(a==1 && sol1(ans^(1ll<<w))) ans^=(1ll<<w);
        else if(a!=1 &&sol2(ans^(1ll<<w))) ans^=(1ll<<w);
    }
    cout<<ans<<'\n';
    return;
}


int main()
{
	// foropen("input.txt" , "r" , stdin);
	// foropen("output.txt" , "w" , stdout);

	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    solve();
	
	return 0;	
}

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