oj.uz

Submission #882782

# Submission time Handle Problem Language Result Execution time Memory
882782 2023-12-03T17:47:03 Z Kel_Mahmut Bali Sculptures (APIO15_sculpture) C++14
0 / 100
 1 ms 348 KB 
#include<bits/stdc++.h>
#define pb push_back
#define endl ("\n")
#define all(aa) aa.begin(), aa.end()
typedef long long ll;
using namespace std;

const int maxn = 2005;

int n, l, r;
ll pref[maxn];
bool dp[maxn][maxn];
int dp1[maxn];
ll sum(int a, int b){
	return pref[b] - pref[a-1];
}

bool check(ll val){
	dp[0][0] = 1;

	for(int i = 1; i <= n; i++){
		for(int cnt = 1; cnt <= i; cnt++){
			dp[i][cnt] = 0;
			for(int j = 0; j < i; j++){
				if(dp[j][cnt-1] && ((val & sum(j+1, i)) == 0) )
					dp[i][cnt] = 1;
			}
		}
	}

	bool ret = 0;
	for(int i = l; i <= r; i++){
		ret |=dp[n][i];
	}
	return ret;
}

bool check1(ll val){
	dp1[0] = 0;
	for(int i = 1; i <= n; i++){
		dp1[i] = INT_MAX;
		for(int j = 0; j < i; j++){
			if((sum(j+1, i) & val) == 0)
				dp1[i] = dp1[j] + 1;
		}
	}

	return (dp1[n] > r);
}

int main(){
	cin >> n >> l >> r;
	for(int i = 1; i <= n; i++){
		cin >> pref[i]; pref[i]+=pref[i-1];
	}
	if(l != 1){
		ll cur = 0;
		for(int pw = 62; pw >= 0; pw--){
			if(check(cur + (1ll << pw))) cur+=(1ll<<pw);
		}
		cout << LONG_LONG_MAX - cur<< endl;
	} else{
		ll cur = 0;
		for(int pw = 62; pw >= 0; pw--){
			if(check1(cur + (1ll << pw))) cur+=(1ll<<pw);
		}
		cout << LONG_LONG_MAX - cur<< endl;

	}
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 344 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 348 KB Output is correct
2 Incorrect 0 ms 348 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 344 KB Output is correct
2 Incorrect 1 ms 348 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 348 KB Output is correct
2 Incorrect 0 ms 348 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 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -