Submission #00253


ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
N, M, K = gets.split.map(&:to_i)
P = gets.to_i
if N < 100000
items = [0] * (N + 2)
items[0] = M
P.times do
l, r, c = gets.split.map(&:to_i)
items[l] += c - M
items[r + 1] += M - c
end
(1 .. N + 1).each do |i|
items[i] += items[i - 1]
end
items[0] = 0
(1 .. N + 1).each do |i|
items[i] += items[i - 1]
end
ans = 1e9
(0 .. N - 1).each do |l|
r = (1 .. N).bsearch { |r| items[r] - items[l] >= K }
ans = [ans, r - l].min if r
end
puts ans
exit
end
days = [1]
items = []
item_sums = [0]
P.times do
l, r, c = gets.split.map(&:to_i)
d1 = l - days[-1]
d2 = r - l + 1
days << days[-1] + d1
days << days[-1] + d2
items << M << c
item_sums << item_sums[-1] + M * d1
item_sums << item_sums[-1] + c * d2
end
days << N
items << M
item_sums << item_sums[-1] + (days[-1] - days[-2]) * M
# p days
# p items
# p item_sums
ans = 1e+18
(0 ... 2 * P + 1).each do |l|
ac, wa = 2 * P, l - 1
while wa + 1 < ac
wj = (ac + wa) / 2
sum = item_sums[wj] - item_sums[l]
if sum >= K
ac = wj
else
wa = wj
end
end
sum = item_sums[ac] - item_sums[l]
if sum >= K
day = days[ac] - days[l]
day -= (sum - K) / items[ac - 1]
ans = [ans, day].min
end
end
puts ans

ステータス

項目 データ
問題 0005 - Sand of Star
ユーザー名 magurofly
投稿日時 2021-05-04 22:59:57
言語 Ruby
状態 Wrong Answer
得点 0
ソースコード長 1331 Byte
最大実行時間 464 ms
最大メモリ使用量 7020 KB

セット

セット 得点 Cases
1 ALL 0 / 500 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
hand_made01.txt AC 31 ms 2264 KB
1
hand_made02.txt AC 23 ms 2276 KB
1
hand_made03.txt AC 464 ms 7020 KB
1
hand_made04.txt AC 32 ms 2328 KB
1
hand_made05.txt AC 23 ms 2212 KB
1
in01.txt WA 260 ms 4892 KB
1
in02.txt AC 374 ms 6140 KB
1
in03.txt AC 200 ms 4232 KB
1
in04.txt AC 358 ms 6188 KB
1
in05.txt AC 210 ms 4128 KB
1
in06.txt AC 209 ms 4384 KB
1
in07.txt AC 215 ms 4484 KB
1
in08.txt AC 399 ms 6724 KB
1
in09.txt AC 139 ms 3456 KB
1
in10.txt AC 311 ms 5564 KB
1
in11.txt AC 35 ms 2476 KB
1
in12.txt AC 107 ms 3224 KB
1
in13.txt AC 159 ms 4088 KB
1
in14.txt AC 349 ms 6088 KB
1
in15.txt AC 343 ms 5880 KB
1
in16.txt AC 137 ms 3592 KB
1
in17.txt AC 248 ms 5060 KB
1
in18.txt AC 343 ms 5904 KB
1
in19.txt AC 69 ms 3004 KB
1
in20.txt AC 289 ms 5492 KB
1
in21.txt WA 137 ms 3904 KB
1
in22.txt AC 412 ms 6992 KB
1
in23.txt AC 84 ms 3144 KB
1
in24.txt AC 206 ms 4564 KB
1
in25.txt AC 178 ms 4212 KB
1
in26.txt AC 318 ms 5716 KB
1
in27.txt AC 349 ms 6028 KB
1
in28.txt AC 140 ms 3560 KB
1
in29.txt AC 313 ms 5660 KB
1
in30.txt AC 336 ms 6144 KB
1
sample01.txt AC 25 ms 2460 KB
1
sample02.txt AC 30 ms 2468 KB
1