Submission #304836

#	Time	Username	Problem	Language	Result	Execution time	Memory
304836		Hemimor	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	125 ms	504 KiB

sculpture

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <bitset>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<P,int> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

int n,L,R;
vl a;

bool f(ll x){
	if(L==1){
		vi dp(n+1,inf);
		dp[0]=0;
		for(int i=0;i<n;i++){
			ll t=0;
			for(int j=i;j>=0;j--){
				t+=a[j];
				if((t|x)==x) dp[i+1]=min(dp[i+1],dp[j]+1);
			}
		}
		return dp[n]<=R;
	}
	vvi dp(n+1,vi(n+1));
	dp[0][0]=1;
	for(int i=0;i<n;i++){
		ll t=0;
		for(int j=i;j>=0;j--){
			t+=a[j];
			if((t|x)==x){
				for(int k=0;k<n;k++) if(dp[j][k]) dp[i+1][k+1]=1;
			}
		}
	}
	for(int i=L;i<=R;i++) if(dp[n][i]) return 1;
	return 0;
}

int main(){
	cin>>n>>L>>R;
	a=vl(n);
	for(auto &i:a) cin>>i;
	ll res=(1LL<<44)-1;
	for(int i=43;i>=0;i--) if(f(res-(1LL<<i))) res-=1LL<<i;
	cout<<res<<endl;
}

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