Submission #154210

#	Time	Username	Problem	Language	Result	Execution time	Memory
154210		Arceus113	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	96 ms	588 KiB

sculpture

#include <bits/stdc++.h>
#define int long long
#define MAXN 2005
#define LN 45
#define INF 2000000000000000000
#define MOD 1000000007
#define pb push_back
#define mp make_pair
#define y0 sdkfaslhagaklsldk
#define y1 aasdfasdfasdf
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
using namespace std;
typedef pair<int,int> pp;

int a[MAXN],n,l,r,sum[MAXN],ans=0,mustval=0;
bool dead [LN];
int lg[LN+2];
int dp5[MAXN];
bool dp[MAXN][MAXN];
bool checks (int sum){
	sum=lg[LN]-1-sum;
	//cout<<sum<<' '<<mustval<<'\n';
	if ((sum&mustval) == mustval) return true;
	return false;
}
main(){
	ios::sync_with_stdio(false); cin.tie(0);
	//freopen("inp.txt","r",stdin);
	cin>>n>>l>>r;
	int i,j,k,d;
	for (i=1;i<=n;i++){
		cin>>a[i];
	}
	lg[0]=1; for (i=1;i<=LN;i++) lg[i]=lg[i-1]*2;
	sum[0]=0;
	for (i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];
	if (l == 1){ // sub5
		for (k=LN-1;  k >=0; k--){
			dead[k]=true; mustval+=lg[k];
			dp5[0]=0; for(i=1;i<=n;i++) dp5[i]=INF;
			for (i=0;i<=n;i++){
				for (j=i+1;j<=n;j++){
					if (checks(sum[j]-sum[i])){
						dp5[j]=min(dp5[j],dp5[i]+1);
					} 
				}
			}
			//cout<<k<<' '<<dp[n]<<'\n';
			if (dp5[n] > r){
				dead[k]=false;
				mustval-=lg[k];
				ans+=lg[k];
			}
			else{
				;
			}
		}
		cout<<ans; return 0;
	}
	
	for (k=LN-1;k >=0 ;k--){
		dead[k]=true; mustval += lg[k];
		
		for (i=0;i<=n;i++){
			for (j=0;j<=n;j++) dp[i][j]=false;
		}
		dp[0][0]=true;
		for (i=0;i<=n;i++){
			for (j=0;j<n;j++){
				for (d=i+1;d<=n;d++){
					if (dp[i][j]==true && checks(sum[d]-sum[i])){
						dp[d][j+1]=true;
					}
				}
			}
		}
		bool gg=false;
		for (i=l;i<=r;i++){
			if (dp[n][i]==true) gg=true;
		}
		if (!gg){
			//cout<<k<<'\n';
			dead[k]=false; mustval-=lg[k]; ans+=lg[k];
		}
	}
	cout<<ans;
	return 0;
}
/* Beware of Constants and Constraints. Check again. 
If graph -> da do thi
If Multitest -> eye-check init() function
*/

Compilation message (stderr)

sculpture.cpp:27:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

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