oj.uz

Submission #492748

# Submission time Handle Problem Language Result Execution time Memory
492748 2021-12-08T17:30:14 Z 5AP Bali Sculptures (APIO15_sculpture) C++17
0 / 100
 1 ms 340 KB 
#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(maxn , inf);
bitset<maxn> dp2[maxn];

bool sol1(ll mask){
    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){
    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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 308 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -