[질문] 코포 문제 시간복잡도 질문좀요

[ㅋㅅㅋ(220.74)]

https://codeforces.com/contest/1270/problem/B

이문제인데

https://codeforces.com/blog/entry/72611

튜토리얼은 여기 있거든?

아니 근데 시발 솔루션대로 하면

O(t * n) == O(10000 * 2 * 10^5) 일케되가지고 20억 되서 TLE 나야 하는거 아니냐?

콘테스트때는 방법 알아도 쫄려서 제출 안했는데 이렇게 하는게 답이라니까 다시 생각해도 개빡치네

[ㅋㅅㅋ(220.74)]

루프하는 t는 빼고 배열 길이만으로 계산해야 되는거임;;?

[익명(61.85)]

인풋 마지막줄에 모든 테스트케이스 n 더해도 2×10^5안넘는다고 적혀있음 - dc App

[ㅋㅅㅋ(220.74)]

아 시발 각 배열 수들의 sum이 안넘는다고 해석해버렸네;;

[익명(1.249)]

그거 비슷하게 옛날에는 아예 sum 넘는다는 조건 없었다가 클레임걸려서 넣은 거라고 알고잇슴 애초에 fastio로 비벼도 저정도 시간복잡도를 1초에 견디는게 가능한지도 의문 참고로 저런 조건 없었을때도 테케는 O(tn)에 TLE 안나도록 설계되어있었음..