ფიგურები

დროის ლიმიტი: 1 წმ

მეხსიერების ლიმიტი: 256 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout


მოცემულია 0-ებისა და 1-ებისაგან შედგენილი სტრიქონი, რომლიც უნდა გადააკეთოთ ორგანზომილებიან მასივად და შემდეგ მასში იპოვოთ 1-ებისაგან შედგენილი უდიდესი ფიგურის ფართობი (1-იანების რაოდენობა ამ ფიგურაში). ორგანზომილებიანი მასივი შეგვიძლია წარმოვიდგინოთ როგორც მართკუთხედი, რომელიც ერთეულოვანი ზომის უჯრედებად არის დაყოფილი. ორი 1-იანი ითვლება მეზობლად, თუკი  მათ შესაბამის უჯრედებს საერთო გვერდი აქვთ (ანუ დიაგონალზე მყოფი  1-იანები მეზობლად არ ჩაითვლება). ორი 1-იანი შედის ერთ ფიგურაში, თუ ისინი უკავშირდებიან ერთმანეთს უშუალოდ (მეზობლები არიან) ან სხვა მეზობლების საშუალებით.

შესატანი მონაცემები: პირველ სტრიქონში მოცემულია სტრინგი, რომელიც შედგება 1-ებისა და 0-ებისგან. სტრინგის სიგრძე არ აღემატება 1000000 სიმბოლოს. მეორე სტრიქონში მოცემულია ერთი მთელი რიცხვი, რომელიც აღნიშნავს სვეტების რაოდენობას ორგანზომილებიან მასივში.

გამოსატანი მონაცემები: უდიდესი ფიგურის ფართობი (1-იანების რაოდენობა ამ ფიგურაში).

 

 




მაგალითები

შესატანი მონაცემები
100100010 3 დაკოპირება
გამოსატანი მონაცემები
2 დაკოპირება

შენიშვნა

ეს სტრიქონი გარდაისახება მატრიცაში  და მიიღება შემდეგი მატრიცა

  0

1  0  0

 1  0  

ამ მატრიცაში 1-იანები ადგენენ სულ 2 ფიგურას, ფიგურა1 - (A[0][0], A[1][0]) და ფიგურა2 - (A[1][2]) , მათ შორის უდიდესია ფიგურა 1 და მისი ფართობი  უდრის ორს.

 

 

 

ამოცანა და ტესტები მოამზადა ვალერიან ლიპარტელიანმა.