結果
問題 | No.335 門松宝くじ |
ユーザー | roaris |
提出日時 | 2019-12-11 14:41:40 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,291 bytes |
コンパイル時間 | 184 ms |
コンパイル使用メモリ | 82,204 KB |
実行使用メモリ | 88,732 KB |
最終ジャッジ日時 | 2024-06-24 07:40:53 |
合計ジャッジ時間 | 16,264 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 39 ms
52,560 KB |
testcase_01 | AC | 40 ms
52,472 KB |
testcase_02 | AC | 39 ms
53,932 KB |
testcase_03 | AC | 40 ms
52,904 KB |
testcase_04 | AC | 40 ms
53,484 KB |
testcase_05 | AC | 881 ms
83,616 KB |
testcase_06 | AC | 1,130 ms
84,868 KB |
testcase_07 | AC | 1,543 ms
85,480 KB |
testcase_08 | AC | 1,207 ms
80,584 KB |
testcase_09 | TLE | - |
testcase_10 | TLE | - |
testcase_11 | TLE | - |
testcase_12 | TLE | - |
testcase_13 | TLE | - |
ソースコード
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(self, l, r): #[l:r) L, R = l+self.n, r+self.n res = self.ele while L<R: if R&1: R -= 1 res = self.func(res, self.arr[R-1]) if L & 1: res = self.func(res, self.arr[L-1]) L += 1 L >>= 1 R >>= 1 return res 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)