oj.uz

Submission #766929

# Submission time Handle Problem Language Result Execution time Memory
766929 2023-06-26T09:06:51 Z vito Bali Sculptures (APIO15_sculpture) C++
0 / 100
 1 ms 212 KB 
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAX1=2001;
const int MAX2=101;
const int INF=1e9+5;
int dp1[MAX1];
int dp2[MAX2][MAX2];
vector<int> a(MAX2);
int n, A, B, nas;
ll t=(1LL<<43)-1;
int ok;
int rek1(int i) {
	if(i==n) {
		return 0;
	}
	ll sum=0;
	for(int j=i; j<n; j++) {
		sum+=a[j];
		if((sum|t)==t) {
			dp1[i]=min(dp1[i], 1+rek1(j+1));
		}
	}
	return dp1[i];
}
void rek2(int i, int sof) {
	if(sof==B+1) {
		return;
	}
	if(i==n && sof>=A) {
		ok=1;
		return;
	}
	ll sum=0;
	for(int j=i; j<n; j++) {
		sum+=a[j];
		if((sum|t)==t) {
			if(dp2[j+1][sof+1]) {
				continue;
			}
			dp2[j+1][sof+1]=1;
			rek2(j+1, sof+1);
		}
	}
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> A >> B;
	for(int i=0; i<n; i++) {
		cin >> a[i];
	}
	if(A==1) {
		return 0;
		for(int i=42; ~i; i--) {
			t^=(1LL<<i);
			for(int j=0; j<MAX1; j++) {
				dp1[j]=INF;
			}
			ok=0;
			dp1[n]=0;
			rek1(0);
			if(dp1[0]>B) {
				t^=(1LL<<i);
			}
		}
		cout << t << '\n';
		return 0;
	}
	for(int i=42; ~i; i--) {
		t^=(1LL<<i);
		for(int j=0; j<MAX2; j++) {
			for(int k=0; k<MAX2; k++) {
				dp2[j][k]=0;
			}
		}
		rek2(0, 0);
		if(ok) {
			t^=(1LL<<i);
		}
	}
	cout << t << '\n';
}

Subtask #1
0 / 9.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 25.0

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

Subtask #5
0 / 29.0

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