Submission #582467

#	Time	Username	Problem	Language	Result	Execution time	Memory
582467		NekoRolly	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	114 ms	8400 KiB

sculpture

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e3+4;
 
int n,L,R;
int dp[N][N];
ll pr[N],ans;
 
int Dp1(ll mask){ int f=0;
	for (int i=0; i<=n; i++) for (int j=0; j<=R; j++) dp[i][j] = 0;
	dp[0][0] = 1;
	for (int i=1; i<=n; i++) for (int j=1; j<=R; j++) for (int k=0; k<i; k++)
		dp[i][j] |= dp[k][j-1]&(((pr[i] - pr[k])|mask) == mask);
	for (int i=L; i<=R; i++) f |= dp[n][i];
	return f;
}

int Dp2(ll mask){
	for (int i=1; i<=n; i++) dp[i][0] = N;
	dp[0][0] = 0;
	for (int i=1; i<=n; i++) for (int j=0; j<i; j++) if (((pr[i]-pr[j])|mask) == mask)
		dp[i][0] = min(dp[i][0], dp[j][0] + 1);
	return dp[n][0] <= R;
}
 
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
	cin >> n >> L >> R;
 
	for (int i=1; i<=n; i++){ cin >> pr[i]; pr[i] += pr[i-1];}
 	
	ans = (1ll<<41)-1;
	for (int i=40; i>=0; i--){
		if (L > 1 && Dp1(ans^(1ll<<i))) ans ^= 1ll<<i;
		if (L == 1 && Dp2(ans^(1ll<<i))) ans ^= 1ll<<i;
	}
 
	cout << ans << "\n";
 
    return 0;
}

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