제출 #493946

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
493946		jamezzz	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	447 ms	332 KiB

sculpture

#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#define getchar_unlocked getchar
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(), x.end()
#define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin());
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vll;
mt19937 rng(time(0));

inline int rd(){
    int x=0;
    char ch=getchar_unlocked();
    while(ch<'0'||ch>'9')ch=getchar_unlocked();
    while(ch>='0'&&ch<='9'){
		x=(x<<3)+(x<<1)+ch-'0';
		ch=getchar_unlocked();
	}
    return x;
}

int n,a,b,y[2005];
int maxbit=40;

bool dp1[105][105];//pos,#segment

int msb(ll v){
	for(int i=maxbit;i>=0;--i){
		if(v&(1ll<<i))return i;
	}
	return -1;
}

void solve1(){
	ll ans=0;
	for(int bit=maxbit;bit>=0;--bit){
		memset(dp1,0,sizeof dp1);
		for(int i=a;i<=b;++i)dp1[n+1][i]=1;
		for(int i=n;i>=1;--i){
			for(int j=0;j<=b;++j){
				ll sm=0;
				for(int k=i;k<=n;++k){
					sm+=y[k];
					if(msb(sm&(~ans))<bit)dp1[i][j]|=dp1[k+1][j+1];
				}
			}
		}
		if(!dp1[1][0])ans|=(1ll<<bit);
	}
	pf("%lld\n",ans);
}

int dp2[105];

void solve2(){
	ll ans=0;
	for(int bit=maxbit;bit>=0;--bit){
		for(int i=1;i<=n;++i)dp2[i]=INF;
		for(int i=n;i>=1;--i){
			ll sm=0;
			for(int j=i;j<=n;++j){
				sm+=y[j];
				if(msb(sm&(~ans))<bit)mnto(dp2[i],dp2[j+1]+1);
			}
		}
		if(dp2[1]>b)ans|=(1ll<<bit);
	}
	pf("%lld\n",ans);
}

int main(){
	n=rd();a=rd();b=rd();
	for(int i=1;i<=n;++i)y[i]=rd();
	if(a==1)solve2();
	else solve1();
}

/*
6 1 3
8 1 2 1 5 4
*/

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