oj.uz

Submission #886241

# Submission time Handle Problem Language Result Execution time Memory
886241 2023-12-11T15:39:16 Z tsumondai Bali Sculptures (APIO15_sculpture) C++14
0 / 100
 1 ms 756 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define Task "APIO15_sculpture"
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
#define __TIME  (1.0 * clock() / CLOCKS_PER_SEC)

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 2000 + 5;

const int oo = 1e9, mod = 1e9 + 7;


int n, l, r;
int pref[N];
bool dp[N][N];
int dp1[N];

int sum(int a, int b) {
	return pref[b] - pref[a - 1];
}

bool check(int 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(int val) {
	dp1[0] = 0;
	for (int i = 1; i <= n; i++) {
		dp1[i] = n + 1;
		for (int j = 0; j < i; j++) {
			if ((sum(j + 1, i) & val) == 0)
				dp1[i] = min(dp1[i], dp1[j] + 1);
		}
	}

	return (dp1[n] <= r);
}

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

signed main() {
	cin.tie(0)->sync_with_stdio(false);
	if (fopen(Task".INP", "r")) {
		freopen(Task".INP", "r", stdin);
		freopen(Task".OUT", "w", stdout);
	}
	process();
	cerr << "Time elapsed: " << __TIME << " s.\n";
	return 0;
}

// dont stop

Compilation message

sculpture.cpp: In function 'int main()':
sculpture.cpp:88:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |   freopen(Task".INP", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:89:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |   freopen(Task".OUT", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 9.0

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

Subtask #4
0 / 25.0

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

Subtask #5
0 / 29.0

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