Submission #137664

# Submission time Handle Problem Language Result Execution time Memory
137664 2019-07-28T08:24:11 Z 임유진(#3281) Bitwise (BOI06_bitwise) C++14
30 / 100
1000 ms 380 KB
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;


int main() {
	ios::sync_with_stdio(0);
	int N, P;
	int K[MAXN], A[MAXN], B[MAXN];
	vector<int> cand[MAXN];
	int mult[MAXN];
	int sum[MAXN];
	int v[MAXN];
	int ans = 0;

	cin >> N >> P;
	for(int i = 0; i < P; i++) cin >> K[i];
	for(int i = 0; i < N; i++) cin >> A[i] >> B[i];

	for(int i = 0; i < N; i++) {
		cand[i].push_back(B[i]);
		for(int j = B[i] - 1; j >= A[i]; j--) {
			bool b = true;
			for(auto a : cand[i]) if((j & a) == j) {
				b = false;
				break;
			}
			if(b) cand[i].push_back(j);
		}
		//for(auto a : cand[i]) printf("%d ", a);
		//printf("\n");
	}
	mult[N] = 1;
	for(int i = N - 1; i >= 0; i--) mult[i] = mult[i + 1] * cand[i].size();
	//for(int i = 0; i <= N; i++) printf("%d ", mult[i]);
	//printf("\n");
	sum[0] = 0;
	for(int i = 1; i <= P; i++) sum[i] = sum[i - 1] + K[i - 1];
	for(int i = 0; i < mult[0]; i++) {
		for(int j = 0; j < N; j++) v[j] = cand[j][i % mult[j] / mult[j + 1]];
		//for(int j = 0; j < N; j++) printf("%d ", v[j]);
		//printf("\n");
		int res;
		for(int j = 0; j < P; j++) {
			int bor = 0;
			for(int k = sum[j]; k < sum[j + 1]; k++) bor |= v[k];
			if(j == 0) res = bor;
			else res &= bor;
		}
		ans = max(ans, res);
		//printf("*\n");
	}

	cout << ans;
	return 0;
}

Compilation message

bitwise.cpp: In function 'int main()':
bitwise.cpp:44:7: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
   int res;
       ^~~
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Execution timed out 1042 ms 376 KB Time limit exceeded
8 Execution timed out 1063 ms 256 KB Time limit exceeded
9 Execution timed out 1067 ms 376 KB Time limit exceeded
10 Execution timed out 1073 ms 376 KB Time limit exceeded
11 Incorrect 4 ms 376 KB Output isn't correct
12 Execution timed out 1034 ms 276 KB Time limit exceeded
13 Incorrect 273 ms 380 KB Output isn't correct
14 Execution timed out 1072 ms 256 KB Time limit exceeded
15 Incorrect 2 ms 348 KB Output isn't correct
16 Execution timed out 1082 ms 376 KB Time limit exceeded
17 Execution timed out 1058 ms 376 KB Time limit exceeded
18 Execution timed out 1087 ms 376 KB Time limit exceeded
19 Execution timed out 1079 ms 376 KB Time limit exceeded
20 Execution timed out 1072 ms 256 KB Time limit exceeded