結果
問題 | No.607 開通777年記念 |
ユーザー |
|
提出日時 | 2021-07-01 18:28:40 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,363 bytes |
コンパイル時間 | 92 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 135,836 KB |
最終ジャッジ日時 | 2024-06-28 07:15:32 |
合計ジャッジ時間 | 4,732 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 8 TLE * 1 -- * 1 |
ソースコード
# Should not work in the time limit.N, M = list(map(int, input().split()))inc_dec = []for _ in range(M):inc_dec.append(list(map(int, input().split())))# num_passengers[i][j]: i駅時点でのj番目の車両の乗客数num_passengers = [[0] * N for _ in range(M)]# cum_sum[i][j+1]: i駅の時点での、0番目の車両からj番目の車両までの総乗客数cum_sum = [[0] * (N+1) for _ in range(M)]for j in range(N):num_passengers[0][j] = inc_dec[0][j]cum_sum[0][j+1] = cum_sum[0][j] + num_passengers[0][j]for i in range(1, M):for j in range(N):num_passengers[i][j] = num_passengers[i-1][j] + inc_dec[i][j]cum_sum[i][j+1] = cum_sum[i][j] + num_passengers[i][j]for station in range(M):for start_i in range(N):target = 777 + cum_sum[station][start_i]# 以下のようになるようなxを求める# cum_sum[station][x] - cum_sum[station][start_i] == 777# xの候補の範囲l, r = start_i+1, Nwhile l < r:m = (l + r) // 2if cum_sum[station][m] == target:print('YES')exit()if cum_sum[station][m] < target:l = m + 1else:r = m - 1if cum_sum[station][l] == target:print('YES')exit()print('NO')