Submission #251344

#	Time	Username	Problem	Language	Result	Execution time	Memory
251344		define	Bali Sculptures (APIO15_sculpture)	C++17	71 / 100	112 ms	4352 KiB

sculpture

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define all(v) v.begin(),v.end()
#define P pair<int,int>
#define len(s) (int)s.size()

template<class T> inline bool chmin(T &a, T b){
	if(a>b){a=b;return true;}
	return false;
}
template<class T> inline bool chmax(T &a, T b){
	if(a<b){a=b;return true;}
	return false;
}
constexpr int mod = 998244353;
constexpr int inf = 3e18;

int N,A,B;
int Y[2005];
bool dp[2005][2005];
int dp2[2005];
void solve1(){
	int anti=0;
	rev(i,40){
		anti+=1ll<<i;
		memset(dp,0,sizeof(dp));
		dp[0][0]=true;
		rep(j,N){
			rep(k,B){
				if(!dp[j][k])continue;
				int sum=0;
				for(int l=j;l<N;l++){
					sum+=Y[l];
					if((sum&anti)==0)dp[l+1][k+1]=true;
				}
			}
		}
		bool flag=false;
		for(int j=A;j<=B;j++)flag|=dp[N][j];
		if(!flag)anti^=1ll<<i;
	}
	cout<<(anti^((1ll<<40)-1))<<endl;
}
void solve2(){
	int anti=0;
	rev(i,40){
		anti+=1ll<<i;
		fill(dp2,dp2+N+1,inf);
		dp2[0]=0;
		rep(j,N){
			int sum=0;
			for(int k=j;k<N;k++){
				sum+=Y[k];
				if((anti&sum)==0)chmin(dp2[k+1],dp2[j]+1);
			}
		}
		if(dp2[N]>B)anti^=1ll<<i;
	}
	cout<<(anti^((1ll<<40)-1))<<endl;
}
signed main(){
	cin>>N>>A>>B;
	rep(i,N)cin>>Y[i];
	int ans=0,anti=0;
	if(N<=100)solve1();
	else solve2();
}

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:68:6: warning: unused variable 'ans' [-Wunused-variable]
  int ans=0,anti=0;
      ^~~
sculpture.cpp:68:12: warning: unused variable 'anti' [-Wunused-variable]
  int ans=0,anti=0;
            ^~~~

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