結果
問題 | No.607 開通777年記念 |
ユーザー |
|
提出日時 | 2021-07-01 18:34:51 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 241 ms / 2,000 ms |
コード長 | 1,363 bytes |
コンパイル時間 | 213 ms |
コンパイル使用メモリ | 82,400 KB |
実行使用メモリ | 101,424 KB |
最終ジャッジ日時 | 2024-06-28 07:21:43 |
合計ジャッジ時間 | 2,146 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 10 |
ソースコード
# 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')