AtCoder Beginner Contest D - Redistribution Difficulty: 830
This theme, dynamic programming
It is a problem of so-called typical dynamic programming.
ruby.rb
s = gets.to_i
dp = Array.new(s.next, 0)
dp[0] = 1
s.times do |i|
next if dp[i].zero?
3.upto(s) do |x|
if i + x <= s
dp[i + x] += dp[i]
dp[i + x] %= 1000000007
else
break
end
end
end
puts dp[s]
ruby.rb
if i + x <= s
dp[i + x] += dp[i]
dp[i + x] %= 1000000007
else
break
end
This time it's just fine, so add dp only for ʻi + x <= s`. Python
python.py
from sys import stdin
def main():
input = stdin.readline
s = int(input())
dp = [0] * (s + 1)
dp[0] = 1
for i in range(s):
if dp[i] == 0:
continue
for x in range(3, s + 1):
if i + x <= s:
dp[i + x] += dp[i]
dp[i + x] %= 1000000007
else:
break
print(dp[s])
main()
*** PyPy *** is really fast, isn't it?
| Ruby | Python | PyPy | |
|---|---|---|---|
| Code length(Byte) | 244 | 405 | 405 |
| Execution time(ms) | 284 | 509 | 70 |
| memory(KB) | 14400 | 9060 | 64596 |
Referenced site
Recommended Posts