Problem:


電飾(Illumination)

JOI 高校の文化祭では毎年廊下に電飾が飾られる．電飾は N 個の電球で構成されており，電球は廊下の西側から東側に一列に並んでいる．各電球は明かりがついているか，ついていないかのいずれかの状態である．

JOI 高校の倉庫には電球を操作する機械が眠っている．この機械は電飾内で連続した電球を指定すると，指定された電球のうち，明かりがついている電球全てを明かりがついていない状態にし，明かりがついていない電球全てを明かりがついている状態にする．ただし，機械は老朽化のため，1 回しか使用できない．

JOI 高校の生徒達は明かりがついている電球とついていない電球が交互に並んだ列（このような電球の列を交互列と呼ぶ）が好きである．そこで，この機械を必要ならば1 回だけ使って，できるだけ長い交互列を含む電飾を作ることにした．

例

例えば，電飾の配置が西から東に向かって

となっていたとする（○は明かりがついている電球を，●は明かりがついていない電球を表す）．このとき，4 番目から7 番目までの4 個の電球に対して機械を操作すると，

となり，2 番目から8 番目までの電球が長さ7 の交互列をなす．

また，8 番目の電球のみに対して機械を操作すると，

となり，4 番目から10 番目までの電球が長さ7 の交互列をなす．

機械を最大1 回使用することで，長さが8 以上の交互列を作ることはできない．

課題

電飾の情報が与えられたとき，機械を最大1 回使用することで得られる電球の配列に含まれる交互列の長さとして考えられるものの最大値を求めるプログラムを作成せよ．

制限

2 ≤ N ≤ 100 000      電飾を構成する電球の個数

入力

標準入力から以下のデータを読み込め．

 1 行目には整数 N が書かれている．

 2 行目には N 個の 0 または 1 が空白を区切りとして書かれている．各整数は機械を操作する前における電球の情報を表している．左からi ( 1 ≤ i ≤ N ) 番目の整数は西側から i 番目の電球の情報を表しており，整数が 1 ならば電球の明かりがついていて，0 ならば明かりがついていないことを表す．

出力

標準出力に，作成可能な電球の列に含まれる交互列の長さの最大値を表す整数を1 行で出力せよ．

入出力例

入力例 1

10
1 1 0 0 1 0 1 1 1 0

 出力例 1

7

これは問題文中で説明された例である．

入力例 2

10
1 0 0 0 0 1 0 1 0 1

出力例 2

8

西側から 4 番目の電球のみを操作すると，最大値 8 を満たす交互列が得られる．

入力例 3

5
1 1 0 1 1

出力例 3

5

西側から数えて 2 番目から 4 番目までの電球を操作すると，全ての電球からなる交互列を作ることがで
きる．

入力例 4

3
0 1 0

出力例 4

3

機械を使用しなくても良い場合があることに注意せよ．

問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。



Sample input:
10
1 1 0 0 1 0 1 1 1 0


Sample output:
7

Submission status: Wrong Answer

Solution code:
N = int(input())
dl = list(map(str, input().split()))
ans = 1
def search(d):
    global ans
    for i in range(N):
        k = 1
        for j in range(i+1, N):
            if d[j-1] != d[j]:
                k += 1
                if ans < k:
                    ans = k
                    if ans == 8:
                        return
            else:
                k = 1

def search2():
    global ans
    for i in range(N):
        for j in range(i+1, N-1):
            if dl[j-1] == dl[j] and dl[j] == dl[j+1]:
                t = [y for y in dl]
                t[j] = "1" if t[j] == "0" else "0"
                search(t)
                if ans == 8:
                    return

def search3():
    global ans
    for i in range(N):
        x = -1
        for j in range(i+1, N):
            if dl[j-1] == dl[j]:
                x = j
            if x != -1:
                t = [y for y in dl]
                for a in range(x, j+1):
                    t[a] = "1" if t[a] == "0" else "0"
                    search(t)
                    if ans == 8:
                        return

search(dl)
if ans != 8:
    search2()
if ans != 8:
    search3()
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
dl = list(map(str, input().split()))
ans = 1
def search(d):
    tmp = 1
    for i in range(N):
        k = 1
        for j in range(i+1, N):
            if d[j-1] != d[j]:
                k += 1
                if tmp < k:
                    tmp = k
                    if tmp == 8:
                        return tmp
            else:
                k = 1
    return tmp
 
ans = search(dl)
 
for i in range(N):
    for j in range(i+1, N-1):
        if dl[j-1] == dl[j] and dl[j] == dl[j+1]:
            t = [y for y in dl]
            t[j] = "1" if t[j] == "0" else "0"
            ret = search(t)
            if ans < ret:
                ans = ret
                if ans == 8:
                    break
 
for i in range(N):
    x = -1
    for j in range(i+1, N):
        if dl[j-1] == dl[j]:
            x = j
        if x != -1:
            t = [y for y in dl]
            for a in range(x, j+1):
                t[a] = "1" if t[a] == "0" else "0"
                ret = search(t)
                if ans < ret:
                    ans = ret
                    if ans == 8:
                        break
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
dl = list(map(str, input().split()))
ans = 1
def search(d):
    tmp = 1
    for i in range(N):
        k = 1
        for j in range(i+1, N):
            if d[j-1] != d[j]:
                k += 1
                if tmp < k:
                    tmp = k
            else:
                k = 1
    return tmp

ans = search(dl)

for i in range(N):
    for j in range(i+1, N-1):
        if dl[j-1] == dl[j] and dl[j] == dl[j+1]:
            t = [y for y in dl]
            t[j] = "1" if t[j] == "0" else "0"
            ret = search(t)
            if ans < ret:
                ans = ret

for i in range(N):
    x = -1
    for j in range(i+1, N):
        if dl[j-1] == dl[j]:
            x = j
        if x != -1:
            t = [y for y in dl]
            for a in range(x, j+1):
                t[a] = "1" if t[a] == "0" else "0"
                ret = search(t)
                if ans < ret:
                    ans = ret

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
dl = list(map(str, input().split()))
ans = 1
def search(d):
    tmp = 1
    for i in range(N):
        k = 1
        for j in range(i+1, N):
            if d[j-1] != d[j]:
                k += 1
                if tmp < k:
                    tmp = k
                   
            else:
                k = 1
    return tmp
 
ans = search(dl)
 
for i in range(N):
    for j in range(i+1, N-1):
        if dl[j-1] == dl[j] and dl[j] == dl[j+1]:
            t = [y for y in dl]
            t[j] = "1" if t[j] == "0" else "0"
            ret = search(t)
            if ans < ret:
                ans = ret
            
 
for i in range(N):
    x = -1
    for j in range(i+1, N):
        if dl[j-1] == dl[j]:
            x = j
        if x != -1:
            t = [y for y in dl]
            for a in range(x, j+1):
                t[a] = "1" if t[a] == "0" else "0"
                ret = search(t)
                if ans < ret:
                    ans = ret
                 
 
print(ans)

Submission status: Accepted

Solution code:
n=int(raw_input())
il=map(int,raw_input().split())
s=0
t=0
cnt=[]
while t<n-1:
    if il[t]==il[t+1]:
        cnt.append(t+1-s)
        s=t+1
    t+=1
    if t==n-1:
        cnt.append(t+1-s)
ans=0
if len(cnt)<=3:
    print(sum(cnt))
else:
    for i in xrange(len(cnt)-2):
        ans=max(ans,cnt[i]+cnt[i+1]+cnt[i+2])
    print(ans)

Submission status: Accepted

Solution code:
n=int(raw_input())
il=map(int,raw_input().split())
s=0
cnt=[]
for t in xrange(n):
    if t==n-1:
        cnt.append(t+1-s)
        break
    if il[t]==il[t+1]:
        cnt.append(t+1-s)
        s=t+1
ans=0
if len(cnt)<=3:
    print(sum(cnt))
else:
    for i in xrange(len(cnt)-2):
        ans=max(ans,cnt[i]+cnt[i+1]+cnt[i+2])
    print(ans)

Submission status: Accepted

Solution code:
n, lights = int(input()), input().split()
con, seq = 1, []
prev = lights.pop()
while lights:
    light = lights.pop()
    if light == prev:
        seq.append(con)
        con = 1
    else:
        con += 1
    prev = light
seq.append(con)
if len(seq) <= 3:
    print(sum(seq))
else:
    print(max(sum(seq[i:i + 3]) for i in range(len(seq) - 2)))

Submission status: Accepted

Solution code:
n=int(input())
a=input().split()
p=a.pop();c=1;d=[]
while a:
    if a[-1]==p:d+=[c];c=1
    else:c+=1
    p=a.pop()
d+=[c]
if len(d)<=3:print(sum(d))
else:
    print(max(sum(d[i:i+3]) for i in range(len(d)-2)))

Submission status: Accepted

Solution code:
N = int(input())
*A, = map(int, input().split())
for i in range(N): A[i] ^= i&1
B = []
prev = A[0]; cnt = 0
for i in range(N):
    if prev != A[i]:
        B.append(cnt)
        cnt = 1
    else:
        cnt += 1
    prev = A[i]
B.append(cnt)
if len(B) == 1:
    print(B[0])
elif len(B) == 2:
    print(B[0] + B[1])
else:
    print(max(B[i]+B[i+1]+B[i+2] for i in range(len(B)-2)))

Submission status: Accepted

Solution code:
# AOJ 0603 Illumination
# Python3 2018.7.2 bal4u

import sys
from sys import stdin
input = stdin.readline

n = int(input())
a = list(map(int, input().split()))
t, k = [], 0
for i in range(n):
	if k > 0:
		if a[i] == a[i-1]:
			t.append(k)
			k = 0
	k += 1
if k > 0: t.append(k)
ans = k = 0
for i in range(len(t)):
	k += t[i]
	if i > 2: k -= t[i-3]
	ans = max(ans, k)
print(ans)

Submission status: Accepted

Solution code:
_ = input()
A = [0]
b = ''

for a in input().split():
    if b == '' or b == a:
        A.append(1)
    else:
        A[-1] += 1
    b = a

ans = 0
if len(A) < 5:
    ans = sum(A)
else:
    for i in range(1, len(A)-2):
        ans = max(ans, sum(A[i:i+3]))

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))

dp = [[1]*3 for i in range(n)]
ans = 1
for i in range(n-1):
    for j in range(3):
        if a[i] != a[i+1]:
            if dp[i+1][j] < dp[i][j] + 1:
                dp[i+1][j] = dp[i][j] + 1
        if j<2 and a[i] == a[i+1]:
            if dp[i+1][j+1] < dp[i][j] + 1:
                dp[i+1][j+1] = dp[i][j] + 1
for v in dp:
    t = max(v)
    if ans < t:
        ans = t
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a  = list(map(int,input().split()))
d = []
l = 0
for i in range(n-1):
    if a[i+1] == a[i]:
        r =  i+1
        d.append(r-l)
        l = r
d.append(n-l)
ans = 0

for i in range(len(d)-2):
    ans = max(ans,d[i]+d[i+1]+d[i+2])
if len(d) == 2:
    ans = max(d[0]+d[1],ans)
    ans = max(d[-1]+d[-2],ans)
if len(d) == 1:
    ans = d[0]
    
print(ans)

Submission status: Accepted

Solution code:
#A
N = int(input())
S = list(map(int,input().split()))

R = []
now = 1
for i in range(N-1):
    if S[i] != S[i+1]:
        now+=1
    else:
        R.append(now)
        now = 1
        
R.append(now)
#print(R)
RL = len(R)
ans = 0
for i in range(RL):
    if i == 0:
        if RL == 1:
            ans = R[0]
        else:
            ans = R[i]+R[i+1]
    elif i == RL-1:
        ans = max(ans,R[i]+R[i-1])
    else:
        ans = max(ans,R[i-1]+R[i]+R[i+1])
        
print(ans)

Submission status: Accepted

Solution code:
# AOJ0603

illu = []
n = 0

def findmax(begin, end):
    flag = illu[begin]
    l = 1
    maxlen = 1
    for i in range(begin + 1, end + 1):
        if illu[i] + flag == 1:
            l += 1
        else:
            if l > maxlen:
                maxlen = l
            l = 1
        flag = illu[i]
    return maxlen if maxlen > l else l

def find_alterseq():
    seq = []
    s = e = 0
    flag = illu[0]
    for i in range(1, n + 1):
        if illu[i] + flag != 1:
            seq.append([s, i - 1])
            s = i
        flag = illu[i]
    return seq
        
def reverse(s, e):
    for i in range(s, e + 1):
        illu[i] = 1 - illu[i]

def solve():
    alseq = find_alterseq()
    maxlen = 0
    alseq.insert(0, [0, 0])
    alseq.append([n, n])
    nindex = len(alseq)
    for i in range(1, nindex - 1):
        s, e = alseq[i]
        begin = alseq[i - 1][0]
        end = alseq[i + 1][1]
        if end - begin + 1 >= maxlen:
            reverse(s, e)
            l = findmax(begin, end)
            if l > maxlen:
                maxlen = l
            reverse(s, e)
    return maxlen

line = input()
n = int(line)
illu = list(map(int, list(input().split())))
illu.append(999)
ans = solve()
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
l_c=[0]
c=1
for i in range(1,n):
    if l[i]==l[i-1]:
        l_c.append(c)
    c+=1
l_c.append(c)
if len(l_c)<5:
    print(n)
else:
    ans=-1
    for i in range(len(l_c)-3):
        ans=max(ans,l_c[i+3]-l_c[i])
    print(ans)

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int, input().split()))
dp = [[0]*3 for _ in [0]*N]
dp[0] = [1, 1, 1]
ans = 0

for i, (n1, n2) in enumerate(zip(a, a[1:]), start=1):
    if n1 != n2:
        for j in range(3):
            dp[i][j] = dp[i-1][j]+1
    else:
        dp[i][0] = 1
        if dp[i-1][2] > ans:
            ans = dp[i-1][2]
        for j in range(2, 0, -1):
            dp[i][j] = dp[i-1][j-1]+1

print(max(max(dp[-1]), ans))