結果

問題 No.335 門松宝くじ
ユーザー soupesuteakasoupesuteaka
提出日時 2016-02-25 17:50:24
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 377 ms / 2,000 ms
コード長 2,336 bytes
コンパイル時間 246 ms
コンパイル使用メモリ 82,124 KB
実行使用メモリ 92,140 KB
最終ジャッジ日時 2024-09-22 13:42:40
合計ジャッジ時間 4,008 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 54 ms
64,468 KB
testcase_01 AC 55 ms
64,956 KB
testcase_02 AC 54 ms
64,320 KB
testcase_03 AC 53 ms
64,924 KB
testcase_04 AC 54 ms
64,056 KB
testcase_05 AC 218 ms
83,408 KB
testcase_06 AC 296 ms
85,308 KB
testcase_07 AC 283 ms
90,684 KB
testcase_08 AC 157 ms
88,544 KB
testcase_09 AC 367 ms
92,140 KB
testcase_10 AC 372 ms
91,440 KB
testcase_11 AC 368 ms
91,036 KB
testcase_12 AC 377 ms
91,564 KB
testcase_13 AC 368 ms
91,660 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
			emi = E[m][i]
			emj = E[m][j]
			if (emi < emj):
				if (i==0):
					tmp = 0
				else:
					tmp = leftmaxs[i-1]
				if (tmp > emi):
					maximam = max(emi,emj,tmp, maximam)

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

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

				if (j+1>=N):
					tmp = N+1
				else:
					tmp = rightmins[j+1]
				if (tmp < emj):
					maximam = max(emi,emj,tmp, maximam)

			else:
				if (i==0):
					tmp = N+1
				else:
					tmp = leftmins[i-1]
				if (tmp < emi):
					maximam = max(emi,emj,tmp, maximam)

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

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

				if (j+1>=N):
					tmp = 0
				else:
					tmp = rightmaxs[j+1]
				if (tmp > emj):
					maximam = max(emi,emj,tmp, maximam)

			ans += maximam

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

print (idx)
0