pastebin

Paste Search Dynamic
Recent pastes
as
  1. require 'set'
  2. def f(m)
  3.         ac=0
  4.         dc=0
  5.         s=0
  6.         dp=[]
  7.         12.times{
  8.                 dp<<Array.new(12,0)
  9.         }
  10.        
  11.         12.times{|x|
  12.                 if m[0][x]=="0" then
  13.                         s=0
  14.                 else
  15.                         if s==0 then
  16.                                 s=1
  17.                                 ac+=1
  18.                                 dp[0][x]=ac
  19.                         else
  20.                                 dp[0][x]=ac
  21.                         end
  22.                 end
  23.         }
  24.         1.upto(11){|y|
  25.                 n=-1
  26.                 d=0
  27.                 ss=set.new()
  28.                 13.times{|x|
  29.                        
  30.                         if x==12 || m[y][x]=="0" then
  31.                                 ac=1 if ac==0 && n!=-1
  32.                                 if n!=-1 && ss.size>1 then
  33.                                         dc+=ss.size
  34.                                 end
  35.                                 ss.clear
  36.                                 n=-1
  37.                         else
  38.                                 c=m[y][x]
  39.                                 c2=m[y-1][x]
  40.                                 if n==-1 then
  41.                                         if c2=="1" then
  42.                                                 dp[y][x]=dp[y-1][x]
  43.                                         else
  44.                                                 ac+=1
  45.                                                 dp[y][x]=ac
  46.                                                 ss<<n
  47.                                         end
  48.                                         n=dp[y][x]
  49.                                        
  50.                                 else
  51.                                         if c2=="1" then
  52.                                                 n=dp[y-1][x] if n>dp[y-1][x]
  53.                                                 ss<<dp[y-1][x]
  54.                                         end
  55.                                         dp[y][x]=n
  56.                                 end
  57.                         end
  58.                 }
  59.  
  60.                 n=-1
  61.                 11.downto(0){|x|
  62.                         c=m[y][x]
  63.                         if c=="0" then
  64.                                 n=-1
  65.                         else
  66.                                 if n==-1 then
  67.                                         n=dp[y][x]
  68.                                 else
  69.                                         dp[y][x]=n
  70.                                 end
  71.                         end
  72.                 }
  73.  
  74.         }
  75.         puts ac-dc
  76. end
  77. while s=gets
  78.         as=[s.chomp]
  79.         while s=gets
  80.                 s=s.chomp
  81.                 break if s==""
  82.                 as<<s
  83.         end
  84.         f(as)
  85. end
Parsed in 0.018 seconds