[일반] 오늘 하루종일 붙잡은 문제

[익명(222.109)]

https://usaco.org/index.php?page=viewproblem2&cpid=923

USACO

진작에 포기하고 자체 솔루션 봤는데 특정 부분 너무 헷갈려서 계속 봄

한참 하다가 USACO guide 솔루션 보니까 여기가 훨씬 친절하게 잘나와있더라

솔루션은 https://usaco.guide/problems/usaco-923-painting-the-barn/solution

메인은 2D prefix sum 인데 존나 헷갈린다 진짜

[익명(115.92)]

링크 들어가서 문제 읽어보는데 지문이 이해가 안되네;; N개 직사각형있고 K개 직사각형으로 이걸 다 덮을 수 있다는건가? 거기서 2개 직사각형 더 그려서 K개로 여전히 다 덮을 수 있게 할 때 최대 영역 구하는거임? 잘못 이해한 거면 설명좀 해주라..