oj.uz

Submission #212682

# Submission time Handle Problem Language Result Execution time Memory
212682 2020-03-24T05:22:55 Z spdskatr Bali Sculptures (APIO15_sculpture) C++14
0 / 100
 5 ms 384 KB 
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;
typedef long long ll;

int N, A, B, y[2005], dp[105][105];
int seen[2005], dists[2005];
ll ps[2005];
queue<int> bfs;

int solve(ll mask, int bit) {
	if (N <= 100) {
		memset(dp, 0, sizeof(dp));
		dp[0][0] = 1;
		for (int i = 1; i <= N; i++) {
			for (int k = 1; k <= B; k++) {
				for (int j = 1; j <= i; j++) {
					if (((ps[i] - ps[j-1]) ^ mask) <= ((1LL << bit) - 1)) {
						dp[i][k] |= dp[j-1][k-1];
					}
				}
			}
		}
		for (int k = A; k <= B; k++) if (dp[N][k]) return 1;
		return 0;
	} else {
		memset(seen, 0, sizeof(seen));
		seen[0] = 1;
		bfs.push(0);
		while (!bfs.empty()) {
			int i = bfs.front(); bfs.pop();
			if (dists[i] == B) continue;
			for (int j = i+1; j <= N; j++) {
				if (!seen[j] && ((ps[j] - ps[i]) ^ mask) <= ((1LL << bit) - 1)) {
					seen[j] = 1;
					dists[j] = dists[i] + 1;
					bfs.push(j);
				}
			}
		}
		return seen[N];
	}
}

int main() {
	scanf("%d %d %d", &N, &A, &B);
	for (int i = 1; i <= N; i++) {
		scanf("%d", y+i);
		ps[i] = ps[i-1] + y[i];
	}
	ll res = 0;
	for (int b = 42; b >= 0; b--) {
		if (!solve(res, b)) res |= (1LL << b);
	}
	printf("%lld\n", res);
}

Compilation message

sculpture.cpp: In function 'int main()':
sculpture.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &N, &A, &B);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", y+i);
   ~~~~~^~~~~~~~~~~

Subtask #1
0 / 9.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 25.0

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

Subtask #5
0 / 29.0

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