Submission #1236746

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236746		ZeroCool	Bali Sculptures (APIO15_sculpture)	C++20	100 / 100	107 ms	21668 KiB

sculpture

#include <bits/stdc++.h>
using namespace std;;
#define ll long long
#define ar array
#define ld long double
#define int long long
#define all(v) v.begin(), v.end()

const int N = 3e5 + 20;
const int M = 20;
const int LOG = 40;
const int INF = 1e17;	
int MOD = 1e9 + 7;
const ld EPS = 1e-12;

template<typename T>
inline void chmin(T &x,T y){x = min(x, y);}
template<typename T>
inline void chmax(T &x,T y){x = max(x, y);}
inline void mm(int &x){x = (x % MOD + MOD) % MOD;};

int n, a, b;
int A[N];

void sub1(){
	int ans = 0;

	for(int k = LOG;k >= 0;k--){
		bool dp[n + 1][n + 1];
		memset(dp, 0, sizeof dp);
		dp[0][0] = 1;
		for(int i = 0;i < n;i++){
			for(int j = 0;j < n;j++){
				//if(k == 1)cout<<dp[i][j];
				if(!dp[i][j])continue;
				int sum = 0;
				for(int x = i;x < n;x++){
					sum += A[x];
					int s = sum;
					s >>=k;
					s <<= k;
					s |= ans;
					if(s == ans){
						//if(k == 1)cout<<i<<" "<<x<<" "<<sum<<'\n';
						dp[x + 1][j + 1] = 1;
					}
				}
			}
			//if(k == 1)cout<<'\n';
		}
		bool f = 0;
		for(int i = a;i <= b;i++){
			if(dp[n][i]) f = 1;
		}
		if(!f)ans += (1ll << k);
	}

	cout<<ans<<'\n';
}
void sub2(){
	int ans = 0;
	for(int k = LOG ;k >= 0;k--){
		vector<int> g[n + 1];
		for(int i = 0;i < n;i++){
			int sum = 0;
			for(int j = i;j < n;j++){
				sum += A[j];
				int s = sum;
				s >>=k;
				s <<= k;
				s |= ans;
				if(s == ans)g[i].push_back(j + 1);
			}
		}
		int dp[n + 1];
		memset(dp, 0x3f, sizeof dp);
		dp[0] = 0;
		for(int i = 0;i < n;i++){
			for(auto u: g[i])chmin(dp[u], dp[i] + 1);
		}
		//cout<<k<<" "<<dp[n]<<'\n';
		if(dp[n] > b)ans += (1ll << k);	
	}
	cout<<ans;
}

void orz(){
	cin>>n>>a>>b;
	for(int i = 0;i < n;i++)cin>>A[i];
	if(a != 1)sub1();
	else sub2();
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t = 1;
	//cin>>t;
	while (t--)orz();
}//DAG dp for n > 100, n^3 dp for n < 100

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