oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

ladybugs Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

ladybugs.html

Problem Description

Jianzhi was walking around in a garden one day, when he found a line of N ladybugs, each with a mysterious integer written onto it (what?). The ith ladybug from the front has the integer Ai. Through the use of his high-level experimental techniques, he managed to deduce that two ladybugs can only communicate with one another if the integers they carry have a bitwise AND of 0.

He notices that if he randomly removes one ladybug from the line, the two ladybugs in front and behind it will come together and make the line complete again. Jianzhi would like to remove some ladybugs, such that any two adjacent ladybugs are able to communicate with one another, and he also wants to leave the maximum possible number of ladybugs in the line. Help Jianzhi find out what is the maximum number of ladybugs he can leave in the line.

Limits

Subtask 1 (26%): 1 ≤ N ≤ 20, 0 ≤ Ai ≤ 109.

Subtask 2 (22%): 1 ≤ N ≤ 2000, 0 ≤ Ai ≤ 109. All Ai will be equal.

Subtask 3 (52%): 1 ≤ N ≤ 2000, 0 ≤ Ai ≤ 109.

Subtask 4 (0%): Sample Testcases

Input

The first line of input will contain one integer, N.

The second line of input will contain N integers, representing the array A.

Output

The output should contain exactly one integer, the maximum number of ladybugs Jianzhi can leave in the line.

Sample Testcase 1

Input

5
2 1 3 4 6

Output

3

Explanation

Jianzhi can leave the line [2, 1, 4].

Sample Testcase 2

Input

7
2 4 3 2 0 3 4

Output

6

Explanation

Jianzhi can leave the line [2, 4, 2, 0, 3, 4].

Tags

Dynamic Programming

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
126221s256MBMinimum
222201s256MBMinimum
352621s256MBMinimum
4021s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o ladybugs -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.