뭔가 처음에 너무 이분탐색적인 느낌의 지문이라
이분탐색 생각하다가
간선 제거보다는 간선 연결이 쉽지 하면서
유니온 파인드로 간선 연결할 생각하고
똥꼬쇼하면서 구현했는데
ㅅㅂ 그냥 간선제거방향으로 생각해볼걸 ㅅㅂㅅㅂ
1시간정도 걸려서 생각 정리하고 구현했는데
b번은 뭔가 내가 생각한게 가장 크기가큰 subarray찾아서
걔 양옆의 음수중에 하나라도 그 합이 커지면 음수에 더하고 아니라면 그냥 subarray 몸집 늘리기를 할건데
양옆의 음수중에 더 몸집 커지는 쪽으로 해당 음수에 더하면 된다고 생각했었음..
근데 이거 구현 어케함? ㅋㅋ 일단 내 생각을 시간복잡도 안에 구현하는게 안떠올라서 그냥 잘못 생각했나보다 하고 C로 넘겼음ㅋㅋ
- dc official App
부분합최대 구하는건 웰노운 dp
부분합 최대는 누적합 dp가 음수면 끊고 양수면 있는 dp아님? - dc App
아 맞음
잇는 - dc App
근데 그걸 K번 더해야되잖아 그럼 수정사항 반영을 어케함? - dc App
근데 암튼 그 최댓값을 계속 넣어주고 또 최댓값 늘리고 또 넣어주고...를 반복하는게 최적
그러므로 원래 합인 sum에 2배씩 커지는 최댓값을 계속 더해주면 됨
그냥 그거만 따로 계산하면서 더하면 됨 ㅇㅅㅇ
k는 전체테케에서 n과 독립적으로 20만 이하이므로... 시간내에 동작함
나는 음수쪽에 더해주면 부분합최대가 수정될 수도 있다고 생각했는데 애초에 그럴리가 없었구나? 부분합 최대라는것 부터가 주변 음수에 아무리 더해봤자 본인 스스로에게 더하는걸 이길수가 없네? - dc App
아하 거길 오해햇군
난 병신인가??? 난 병신인가??? 난 병신인가??? 조금만 더 생각했으면 B번이라도 푸는거였는데 난 병신인가?? - dc App
kadane algorithm
print((sum(A)+mx*pow(2, K, mod)-mx+mod)%mod)