結果

問題 No.335 門松宝くじ
コンテスト
ユーザー soupesuteaka
提出日時 2016-02-25 08:30:21
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,647 bytes
コンパイル時間 226 ms
コンパイル使用メモリ 82,340 KB
実行使用メモリ 99,236 KB
最終ジャッジ日時 2024-09-22 13:38:53
合計ジャッジ時間 4,004 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 1 TLE * 1 -- * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import re
import itertools

""" defs """
class SegTree_Min:
	def __init__(self, n):
		self.n = 1
		while (self.n < n):
			self.n <<= 1
		self.dat = [float('inf')] * (2*self.n-1)

	def update(self, x, k):
		k += self.n - 1
		self.dat[k] = x
		while(k > 0):
			if (self.dat[(k-1)//2] > self.dat[k]):
				self.dat[(k-1)//2] = self.dat[k]
			k = (k-1) // 2

	def query_rec(self, a, b, k, l, r):
		if (b <= l or r <= a):
			return float('inf')
		if (a<=l and r <= b):
			return self.dat[k]

		left = self.query_rec(a, b, k*2+1, l, (l+r)//2)
		right = self.query_rec(a, b, k*2+2, (l+r)//2, r)
		return min(left, right)

	def query(self, a, b):
		return self.query_rec(a, b, 0, 0, self.n)

class SegTree_Max:
	def __init__(self, n):
		self.n = 1
		while (self.n < n):
			self.n <<= 1
		self.dat = [0] * (2*self.n-1)

	def update(self, x, k):
		k += self.n - 1
		self.dat[k] = x
		while(k > 0):
			if (self.dat[(k-1)//2] < self.dat[k]):
				self.dat[(k-1)//2] = self.dat[k]
			k = (k-1) // 2

	def query_rec(self, a, b, k, l, r):
		if (b <= l or r <= a):
			return 0
		if (a<=l and r <= b):
			return self.dat[k]

		left = self.query_rec(a, b, k*2+1, l, (l+r)//2)
		right = self.query_rec(a, b, k*2+2, (l+r)//2, r)
		return max(left, right)

	def query(self, a, b):
		return self.query_rec(a, b, 0, 0, self.n)


""" 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):
	segmin = SegTree_Min(N)
	segmax = SegTree_Max(N)
	for k in range(N):
		segmin.update(E[m][k], k)
		segmax.update(E[m][k], k)

	ans = 0
	for i in range(0, N):
		for j in range(i+1, N):
			maximam = 0
			if (E[m][i] < E[m][j]):
				tmp = segmax.query(0,i)
				if (tmp > E[m][i]):
					maximam = max(E[m][i],E[m][j],tmp, maximam)
				tmp = segmin.query(i,j)
				if (tmp < E[m][i]):
					maximam = max(E[m][i],E[m][j],tmp, maximam)
				tmp = segmax.query(i,j)
				if (tmp > E[m][j]):
					maximam = max(E[m][i],E[m][j],tmp, maximam)
				tmp = segmin.query(j,N)
				if (tmp < E[m][j]):
					maximam = max(E[m][i],E[m][j],tmp, maximam)

			if (E[m][i] > E[m][j]):
				tmp = segmin.query(0,i)
				if (tmp < E[m][i]):
					maximam = max(E[m][i],E[m][j],tmp, maximam)
				tmp = segmax.query(i,j)
				if (tmp > E[m][i]):
					maximam = max(E[m][i],E[m][j],tmp, maximam)
				tmp = segmin.query(i,j)
				if (tmp < E[m][j]):
					maximam = max(E[m][i],E[m][j],tmp, maximam)
				tmp = segmax.query(j,N)
				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