oj.uz

Submission #563576

# Submission time Handle Problem Language Result Execution time Memory
563576 2022-05-17T15:08:12 Z myrcella Bali Sculptures (APIO15_sculpture) C++17
0 / 100
 3 ms 4180 KB 
//by szh
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}

const int maxn = 2e3+10;

int n,A,B;
ll val[maxn];
bool dp1[maxn][maxn];
int dp2[maxn];

bool check(ll mask,ll cur) {
	if (A!=1) {
		dp1[0][0]=1;
		rep(i,1,n+1) {
			rep(j,1,min(B+1,i+1)) {
				dp1[i][j] = 0;
				rep(k,0,i) {
					if (dp1[k][j-1]==1 and ((((val[i]-val[k])>>cur)|mask) == mask)) {
						dp1[i][j]=1;
						break;
					}
				}
				if (dp1[i][j]==1 and i==n and j>=A) return true;
			}
		}
		return false;
	}
	else {
		dp2[0] = 0;
		rep(i,1,n+1) {
			dp2[i] = B+1;
			rep(j,0,i) {
				if ((((val[i]-val[j])>>cur)|mask) == mask) dp2[i] = min(dp2[i],dp2[j]+1);
			}
			if (dp2[i]>B) return false;
		}
		return true;
	}
}

int main() {
//	freopen("input.txt","r",stdin);	

	std::ios::sync_with_stdio(false);cin.tie();
	cin>>n>>A>>B;
	val[0]=0;
	memset(dp1,0,sizeof(dp1));
	rep(i,1,n+1) cin>>val[i],val[i]+=val[i-1];
	ll mask = 0, cur = 40;
	while (cur>=0) {
		mask*=2;
		if (!check(mask,cur)) mask+=1;
		cur--;
	}
	cout<<mask;
	return 0;
}
/*
6 2 3
8 1 2 1 5 4
*/

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Incorrect 2 ms 4180 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Incorrect 2 ms 4180 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4180 KB Output is correct
2 Incorrect 2 ms 4180 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4180 KB Output is correct
2 Incorrect 2 ms 4180 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Incorrect 2 ms 4180 KB Output isn't correct
3 Halted 0 ms 0 KB -