Submission #260971

#	Time	Username	Problem	Language	Result	Execution time	Memory
260971		user202729	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	85 ms	512 KiB

sculpture

// 4
// :(
#ifndef LOCAL
#define NDEBUG 1
#endif
#include<bits/stdc++.h>

int main(){
	std::ios::sync_with_stdio(0);std::cin.tie(0);
	int number, least, most; std::cin>>number>>least>>most;
	std::vector<int64_t> sum(number+1);
	for(auto [index, last]=std::pair(1,(int64_t)0); index<=number; ++index){
		int value; std::cin>>value;
		sum[index]=last+=value;
	}

	auto const check=[&](int64_t const mask){
		if(least!=1){
			std::vector<std::vector<char>> f(number+1, std::vector<char>(most+1));
			f[0][0]=true;
			for(int index=0; index<number; ++index)
				for(int next=index+1; next<=number; ++next)
					if(((~ mask)&(sum[next]-sum[index]))==0){
						for(int numComponent=0; numComponent<most; ++numComponent)
							if(f[index][numComponent]) f[next][numComponent+1]=true;
					}

			return std::any_of(f.back().begin()+least, f.back().end(),[&](auto it){return it;});
		}else{
			std::vector<int> least(number+1, INT_MAX);
			least[0]=0;
			for(int index=0; index<number; ++index) if(auto const curNumber=least[index]; curNumber<most)
				for(int next=index+1; next<=number; ++next)
					if(((~ mask)&(sum[next]-sum[index]))==0){
						least[next]=std::min(least[next], curNumber+1);
					}
			return least.back()<=most;
		}
	};

	int const numBit=1+(63^__builtin_clzll(sum.back()));
	int64_t value=((int64_t)1<<numBit)-1;
	for(int bit=numBit; bit--;){
		if(check(value-((int64_t)1<<bit))) value-=(int64_t)1<<bit;
	}
	std::cout<<value<<'\n';
}

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