結果
問題 | No.335 門松宝くじ |
ユーザー | roaris |
提出日時 | 2019-12-11 14:36:01 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,330 bytes |
コンパイル時間 | 179 ms |
コンパイル使用メモリ | 82,688 KB |
実行使用メモリ | 91,104 KB |
最終ジャッジ日時 | 2024-06-24 07:40:15 |
合計ジャッジ時間 | 3,906 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 39 ms
59,980 KB |
testcase_01 | AC | 39 ms
52,908 KB |
testcase_02 | AC | 40 ms
53,208 KB |
testcase_03 | AC | 41 ms
53,420 KB |
testcase_04 | AC | 39 ms
52,748 KB |
testcase_05 | TLE | - |
testcase_06 | -- | - |
testcase_07 | -- | - |
testcase_08 | -- | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
ソースコード
import sys sys.setrecursionlimit(10**6) class SegmentTree: def __init__(self, N, func): n_ = 1 while n_<N: n_ *= 2 self.n = n_ self.func = func if self.func==max: self.ele = -10**18 elif self.func==min: self.ele = 10**18 self.arr = [self.ele]*(2*self.n-1) def update(self, k, a): k += self.n-1 self.arr[k] = a while k>0: k = (k-1)//2 self.arr[k] = self.func(self.arr[2*k+1], self.arr[2*k+2]) def query_sub(self, a, b, k, l, r): if r<=a or b<=l: return self.ele if a<=l and r<=b: return self.arr[k] else: vl = self.query_sub(a, b, 2*k+1, l, (l+r)//2) vr = self.query_sub(a, b, 2*k+2, (l+r)//2, r) return self.func(vl, vr) def query(self, a, b): return self.query_sub(a, b, 0, 0, self.n) N, M = map(int, input().split()) v_max = -1 ans = -1 for m in range(M): E = list(map(lambda x: x-1, map(int, input().split()))) st_min = SegmentTree(N, min) st_max = SegmentTree(N, max) for i in range(N): st_min.update(i, E[i]) st_max.update(i, E[i]) v = 0 for i in range(N): for j in range(i+1, N): prof = 0 min_1 = st_min.query(0, i) max_1 = st_max.query(0, i) if E[i]>E[j] and min_1<E[i]: prof = max(prof, E[i]) elif E[i]<E[j] and max_1>E[i]: prof = max(prof, max(max_1, E[j])) min_2 = st_min.query(i+1, j) max_2 = st_max.query(i+1, j) if min_2<E[i] and min_2<E[j]: prof = max(prof, max(E[i], E[j])) elif max_2>E[i] and max_2>E[j]: prof = max(prof, max_2) min_3 = st_min.query(j+1, N) max_3 = st_max.query(j+1, N) if E[i]<E[j] and E[j]>min_3: prof = max(prof, E[j]) elif E[i]>E[j] and E[j]<max_3: prof = max(prof, max(E[i], max_3)) v += prof if v>v_max: v_max = v ans = m print(ans)