oj.uz

Submission #563572

# Submission time Handle Problem Language Result Execution time Memory
563572 2022-05-17T14:56:35 Z oolimry Bali Sculptures (APIO15_sculpture) C++17
0 / 100
 1 ms 340 KB 
#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) {
		memset(dp1,0,sizeof(dp1));
		dp1[0][0]=1;
		rep(i,1,n+1) {
			rep(j,0,min(B+1,i+1)) {
				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;
			}
		}
		debug(233);
		return false;
	}
	else {
		memset(dp2,-1,sizeof(dp2));
		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;
	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;
}

Subtask #1
0 / 9.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 25.0

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

Subtask #5
0 / 29.0

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