oj.uz

Submission #583133

# Submission time Handle Problem Language Result Execution time Memory
583133 2022-06-24T21:45:27 Z YesPy Bali Sculptures (APIO15_sculpture) C++17
0 / 100
 1 ms 340 KB 
#include <bits/stdc++.h>

#define mins(i, j) (i = min(i, j))
#define fastio ios::sync_with_stdio(false);cin.tie(nullptr);
#define ln '\n'
#define nwln cout<<ln;

using namespace std;

typedef long long ll;

int N, A, B, dp[2002][2002];
ll ans = 1, pref[2002];

int go1(ll mask) {
	dp[0][0] = 0;
	for(int i=1; i<=N; ++i) dp[i][0] = N;

	for(int i=1; i<=N; ++i) {
		for(int j=0; j<i; ++j) {
			if(((pref[i]-pref[j])|mask) == mask) mins(dp[i][0], (dp[j][0]+1));
		}
	}

	return (dp[N][0] <= B);
}

int go2(ll mask) {
	int res = 0;
	dp[0][0] = 1;

	for(int i=0; i<=N; ++i) {
		for(int j=0; j<=B; ++j) dp[i][j] = 0;
	}

	for(int i=1; i<=N; ++i) {
		for(int j=1; j<=B; ++j) {
			for(int k=0; k<i; ++k) dp[i][j] |= dp[k][j-1] & (((pref[i]-pref[k])|mask) == mask);
		}
	}

	for(int X=A; X<=B; ++X) res |= dp[N][X];
	return res;
}

int main()
{
	fastio
	cin>>N>>A>>B, ans <<= 41, --ans;
	for(int i=1; i<=N; ++i) cin>>pref[i], pref[i] += pref[i-1];

	for(int i=40; i>=0; --i) {
		if(A == 1 && go1(ans^(1LL<<i))) ans ^= (1LL<<i);
		if(A > 1 && go2(ans^(1LL<<i))) ans ^= (1LL<<i);
	}

	cout<<ans<<ln;

	return 0;
}

Subtask #1
0 / 9.0

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

Subtask #2
0 / 16.0

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

Subtask #4
0 / 25.0

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

Subtask #5
0 / 29.0

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