結果

問題 No.335 門松宝くじ
ユーザー soupesuteakasoupesuteaka
提出日時 2016-02-25 10:11:47
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 528 ms / 2,000 ms
コード長 2,431 bytes
コンパイル時間 440 ms
コンパイル使用メモリ 81,864 KB
実行使用メモリ 113,304 KB
最終ジャッジ日時 2023-10-23 19:58:22
合計ジャッジ時間 5,521 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 54 ms
63,360 KB
testcase_01 AC 55 ms
63,360 KB
testcase_02 AC 55 ms
63,360 KB
testcase_03 AC 55 ms
63,360 KB
testcase_04 AC 54 ms
63,360 KB
testcase_05 AC 285 ms
87,900 KB
testcase_06 AC 402 ms
93,544 KB
testcase_07 AC 373 ms
101,420 KB
testcase_08 AC 233 ms
108,604 KB
testcase_09 AC 513 ms
113,304 KB
testcase_10 AC 520 ms
113,216 KB
testcase_11 AC 521 ms
112,732 KB
testcase_12 AC 528 ms
113,164 KB
testcase_13 AC 518 ms
112,524 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import re
import itertools

""" defs """


""" main """
N, M = map(int, input().split())
E = list ( list( map(int,input().split()) ) for _ in range(M) )

idx = 0
maxex = 0

for m in range(M):
	leftmins = [None]*(N)
	rightmins = [None]*(N)
	leftmaxs = [None]*(N)
	rightmaxs = [None]*(N)
	midmins = list ( [None] * (N) for _ in range(N) )
	midmaxs = list ( [None] * (N) for _ in range(N) )

	leftmins[0] = E[m][0]
	for i in range(1, N):
		leftmins[i] = min(leftmins[i-1],E[m][i])
	rightmins[N-1] = E[m][N-1]
	for i in reversed(range(0,N-1)):
		rightmins[i] = min(rightmins[i+1],E[m][i])
	leftmaxs[0] = E[m][0]
	for i in range(1, N):
		leftmaxs[i] = max(leftmaxs[i-1],E[m][i])
	rightmaxs[N-1] = E[m][N-1]
	for i in reversed(range(0,N-1)):
		rightmaxs[i] = max(rightmaxs[i+1],E[m][i])

	for i in range(N):
		midmins[i][i] = E[m][i]
		midmaxs[i][i] = E[m][i]

	for i in range(0,N):
		for l in range(1,N):
			if (i+l>=N):
				break
			midmins[i][i+l] = min(midmins[i][i+l-1],E[m][i+l])
			midmaxs[i][i+l] = max(midmaxs[i][i+l-1],E[m][i+l])

	ans = 0
	for i in range(0, N):
		for j in range(i+1, N):
			maximam = 0
			if (E[m][i] < E[m][j]):
				if (i==0):
					tmp = 0
				else:
					tmp = leftmaxs[i-1]
				if (tmp > E[m][i]):
					maximam = max(E[m][i],E[m][j],tmp, maximam)

				if (i+1>j-1):
					tmp = N+1
				else:
					tmp = midmins[i+1][j-1]
				if (tmp < E[m][i]):
					maximam = max(E[m][i],E[m][j],tmp, maximam)

				if (i+1>j-1):
					tmp = 0
				else:
					tmp = midmaxs[i+1][j-1]
				if (tmp > E[m][j]):
					maximam = max(E[m][i],E[m][j],tmp, maximam)

				if (j+1>=N):
					tmp = N+1
				else:
					tmp = rightmins[j+1]
				if (tmp < E[m][j]):
					maximam = max(E[m][i],E[m][j],tmp, maximam)

			if (E[m][i] > E[m][j]):
				if (i==0):
					tmp = N+1
				else:
					tmp = leftmins[i-1]
				if (tmp < E[m][i]):
					maximam = max(E[m][i],E[m][j],tmp, maximam)

				if (i+1>j-1):
					tmp = 0
				else:
					tmp = midmaxs[i+1][j-1]
				if (tmp > E[m][i]):
					maximam = max(E[m][i],E[m][j],tmp, maximam)

				if (i+1>j-1):
					tmp = N+1
				else:
					tmp = midmins[i+1][j-1]
				if (tmp < E[m][j]):
					maximam = max(E[m][i],E[m][j],tmp, maximam)

				if (j+1>=N):
					tmp = 0
				else:
					tmp = rightmaxs[j+1]
				if (tmp > E[m][j]):
					maximam = max(E[m][i],E[m][j],tmp, maximam)

			ans += maximam

	expectation = ans
	if (idx==-1 or expectation > maxex):
		idx = m
		maxex = expectation

print (idx)
0