Submission #582461

#	Time	Username	Problem	Language	Result	Execution time	Memory
582461		NekoRolly	Bali Sculptures (APIO15_sculpture)	C++17	71 / 100	1090 ms	596 KiB

sculpture

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e3+4;

int n,L,R;
bitset<N> dp[N],aux[N];
ll pr[N],ans;

bool Dp(ll mask){ int f=0;
	for (int i=0; i<=R; i++) dp[i].reset();
	for (int i=1; i<=n; i++) for (int j=0; j<i; j++) aux[i][j] = ((pr[i]-pr[j])|mask) == mask;
	dp[0][0] = 1;
	for (int i=1; i<=n; i++) for (int j=1; j<=R; j++)
		dp[j][i] = (dp[j-1]&aux[i]).count() > 0;
	for (int i=L; i<=R; i++) if (dp[i][n])  return 1;
	return 0;
}

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<<40)-1;
	for (int i=39; i>=0; i--) if (Dp(ans^(1ll<<i))) ans ^= 1ll<<i;

	cout << ans << "\n";

    return 0;
}

Compilation message (stderr)

sculpture.cpp: In function 'bool Dp(ll)':
sculpture.cpp:10:23: warning: unused variable 'f' [-Wunused-variable]
   10 | bool Dp(ll mask){ int f=0;
      |                       ^

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