結果

問題 No.335 門松宝くじ
ユーザー soupesuteakasoupesuteaka
提出日時 2016-02-25 10:11:47
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 516 ms / 2,000 ms
コード長 2,431 bytes
コンパイル時間 371 ms
コンパイル使用メモリ 82,096 KB
実行使用メモリ 114,232 KB
最終ジャッジ日時 2024-09-22 13:39:39
合計ジャッジ時間 4,989 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 54 ms
65,556 KB
testcase_01 AC 54 ms
64,676 KB
testcase_02 AC 54 ms
63,936 KB
testcase_03 AC 53 ms
64,420 KB
testcase_04 AC 54 ms
64,248 KB
testcase_05 AC 265 ms
87,964 KB
testcase_06 AC 379 ms
94,504 KB
testcase_07 AC 364 ms
102,416 KB
testcase_08 AC 223 ms
109,624 KB
testcase_09 AC 506 ms
113,356 KB
testcase_10 AC 509 ms
114,232 KB
testcase_11 AC 507 ms
113,336 KB
testcase_12 AC 516 ms
114,100 KB
testcase_13 AC 515 ms
114,100 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