Submission #212685

#	Time	Username	Problem	Language	Result	Execution time	Memory
212685		spdskatr	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	0 / 100	5 ms	384 KiB

skyscraper

#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++) {
					ll val = ps[i] - ps[j-1];
					if (((val|mask)^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++) {
				ll val = ps[j] - ps[i];
				if (!seen[j] && ((val|mask) ^ 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 (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:52: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);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:54: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 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 43