結果

問題 No.335 門松宝くじ
ユーザー soupesuteakasoupesuteaka
提出日時 2016-02-25 17:48:05
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 427 ms / 2,000 ms
コード長 2,406 bytes
コンパイル時間 1,301 ms
コンパイル使用メモリ 81,596 KB
実行使用メモリ 91,740 KB
最終ジャッジ日時 2023-10-23 20:01:53
合計ジャッジ時間 4,389 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 54 ms
63,508 KB
testcase_01 AC 54 ms
63,508 KB
testcase_02 AC 54 ms
63,508 KB
testcase_03 AC 54 ms
63,508 KB
testcase_04 AC 54 ms
63,508 KB
testcase_05 AC 241 ms
83,540 KB
testcase_06 AC 344 ms
85,156 KB
testcase_07 AC 307 ms
90,028 KB
testcase_08 AC 162 ms
87,768 KB
testcase_09 AC 416 ms
91,288 KB
testcase_10 AC 420 ms
91,672 KB
testcase_11 AC 419 ms
91,200 KB
testcase_12 AC 427 ms
91,740 KB
testcase_13 AC 417 ms
91,344 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#coding: UTF-8

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

leftmins = [0]*(N)
rightmins = [0]*(N)
leftmaxs = [0]*(N)
rightmaxs = [0]*(N)
midmins = list ( [0] * (N) for _ in range(N) )
midmaxs = list ( [0] * (N) for _ in range(N) )

for m in range(M):

	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)

			else:
				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