Problem:


  

  
    MathJax.Hub.Config({ tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]} });
  
  

  

  
B: 全日本帰りたい協会

  
問題

  
株式会社 AOR (Association Of Return home)には $N$ 人の社員がいる。

  

    社員 $i$ はエレベーターを使って $1$ 階に下りたいと考えており、時刻 $t_i$ に $F_i$ 階のエレベーター前にやってくる。あなたは時刻 $0$ に $1$ 階に $1$ 基だけあるエレベーターを遠隔操作し、すべての社員を $1$ 階に送ることにした。エレベーターには $D$ 人までしか乗せられない。
    エレベーターは単位時間に一階分移動するかその場にとどまる事ができる。 社員 $i$ はエレベーターが時刻 $t_i$ に $F_i$ 階にあって、自分が乗っても定員を超過しないときのみエレベーターに乗る。 時刻 $t_i$ にエレベーターに乗れないとき、階段で $1$ 階におりてしまう。 なお、乗り降りにかかる時間は無視できる。
  

  
それぞれの社員がエレベーターに乗っている時間の合計の最小値を求めよ。 ただし、エレベーターで $1$ 階へ運べない人が $1$ 人でもいる場合は $-1$ を出力せよ。

  
制約

  

    
$1 \le N \le 10^5$

    
$1 \le D \le 10^5$

    
$1 \le t_i \lt t_{i+1} \le 10^6$

    
$2 \le F_i \le 10^6$

    
入力は全て整数で与えらえる。

  

  
入力形式

  
入力は以下の形式で与えられる。

  
$N \ D$
$t_1 \ F_1$
$t_2 \ F_2$
$\vdots$
$t_N \ F_N$

  
出力

  
それぞれの社員がエレベーターに乗っている時間の合計の最小値を出力せよ。ただし、エレベーターで $1$ 階へ運べない人が $1$ 人でもいる場合は $-1$ を出力せよ。また、末尾に改行も出力せよ。

  
サンプル

  
サンプル入力 1

  
2 2
2 2
3 3

  
サンプル出力 1

  
5

  
サンプル入力 2

  
2 2
2 2
5 3

  
サンプル出力 2

  
3

  
サンプル入力 3

  
2 2
2 2
3 5

  
サンプル出力 3

  
-1

  

Sample input:
2 2
2 2
3 3


Sample output:
5

Submission status: Wrong Answer

Solution code:
N, D = map(int, input().split())
time = 0
floor = 1
num = 0
result = 0
for _ in [0]*N:
    t, f = map(int, input().split())
    if floor-1+f-1 <= t-time:
        result += num * (floor-1)
        num = 1
    elif abs(floor-f) <= t-time:
        result += num * abs(floor-f)
        num += 1
    else:
        print(-1)
        break
    time, floor = t, f
else:
    result += num * (floor-1)
    print(result)

Submission status: Wrong Answer

Solution code:
N, D = map(int, input().split())
time = 0
floor = 1
num = 0
result = 0
for _ in [0]*N:
    t, f = map(int, input().split())
    if floor-1+f-1 <= t-time:
        result += num * (floor-1)
        num = 1
    elif abs(floor-f) <= t-time and num < D:
        result += num * abs(floor-f)
        num += 1
    else:
        print(-1)
        break
    time, floor = t, f
else:
    result += num * (floor-1)
    print(result)

Submission status: Accepted

Solution code:
# AOJ 2832 All Japan Association of Return home
# Python3 2018.7.12 bal4u

n, d = map(int, input().split())
ans = t0 = f0 = num = 0
for i in range(n):
	t, f = map(int, input().split())
	f -= 1
	df = f-f0
	if df < 0: df = -df
	dt = t - t0
	if dt < df:	ans = -1; break
	if dt >= f0+f:
		ans += num*f0
		num = 0
	else:
		if num+1 > d: ans = -1; break
		ans += num*dt
	f0, t0 = f, t
	num += 1
print(-1 if ans < 0 else ans+num*f0)

Submission status: Accepted

Solution code:
N, D = map(int, input().split())
time = 0
floor = 1
num = 0
result = 0
for _ in [0]*N:
    t, f = map(int, input().split())
    if floor-1+f-1 <= t-time:
        result += num * (floor-1)
        num = 1
    elif abs(floor-f) <= t-time and num < D:
        result += num * abs(t-time)
        num += 1
    else:
        print(-1)
        break
    time, floor = t, f
else:
    result += num * (floor-1)
    print(result)

Submission status: Accepted

Solution code:
n, d = map(int, input().split())
lst = sorted([list(map(int, input().split())) for _ in range(n)]) + [[10 ** 20, 1]]
cnt = 0
time = 0
floor = 1
ans = 0
for i in range(n):
  t, f = lst[i]
  if f - floor > t - time or cnt >= d:
    print(-1)
    break

  ans += cnt * (t - time)
  cnt += 1
  time = t
  floor = f
  next_t, next_f = lst[i + 1]
  if time + (floor - 1) + (next_f - 1) <= next_t:
    ans += cnt * (floor - 1)
    cnt = 0
    time += floor - 1
    floor = 1
else:
  print(ans)