제출 #171689

#제출 시각아이디문제언어결과실행 시간메모리
171689Nodir_BobievBali Sculptures (APIO15_sculpture)C++14
100 / 100
153 ms504 KiB
# include <bits/stdc++.h>
# define FILE

using namespace std;

int n, a, b;
long long y[2010], ans;

bool special_case( long long mask ){
	int mn[2010] = {};
	for( int i = 1; i <= n; i ++ )mn[i] = 1e9;
	for( int i = 1; i <= n; i ++ ){
		for( int j = 1; j <= i; j ++ ){
			if( (mask|(y[i]-y[j-1])) == mask ){
				mn[i] = min( mn[i], mn[j-1] + 1 );
			}
		}
	}
	if( mn[n] <= b ){
		return true;
	}
	else{
		return false;
	}
}

bool check( long long mask ){
	if( a == 1 )return special_case( mask );
	bool dp[n+1][n+1] = {};
	dp[0][0] = 1;
	for( int i = 1; i <= n; i ++ ){
		for( int j = 1; j <= i; j ++ ){
			if( (mask|(y[i]-y[j-1])) == mask ){
				for( int k = 0; k < n; k ++ ){
					if( dp[j-1][k] ) dp[i][k+1] = 1;
				}
			}
		}
	}
	for( int i = a; i <= b; i ++ ){
		if( dp[n][i] )return true;
	}
	return false;
}

int main(){

    # ifdef FILEs
        freopen( "input.txt", "r", stdin );
        freopen( "output.txt", "w", stdout );
    # endif
    ios_base::sync_with_stdio(false);

	cin >> n >> a >> b;
	for( int i = 1; i <= n; i ++ ){
		cin >> y[i];
		y[i] += y[i-1];
	}
	ans = (1ll << 50)-1;
	for( int i = 49; i >= 0; i -- ){
		ans -= (1ll << i);
		if( check( ans ) == false )ans += (1ll << i);
	}
	cout << ans;

}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...