페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8686

전력 공급 1s 256MB

문제

정올국의 발전소는 2차원 좌표평면 위에 있으며,

정올국은 모든 발전소에 전력 P_{init}만큼 공급할 수 있다.

X_i, Y_i에 존재하는 i번 발전소는 R_i만큼 전력을 공급받을 수 있다면,

X_i \le X_j와 Y_i \le Y_j를 만족하는 모든 j번 발전소에 전력 P_i만큼 공급할 수 있다.

i번 발전소가 가동되기 위한 최소 P_{init}을 구하라.


입력

첫 줄에 발전소의 수 N이 주어진다.

다음 N줄에 걸쳐서 i번 발전소 정보가 주어진다.

i번 발전소 정보는 X_i, Y_i, R_i, P_i가 공백을 구분으로 주어진다.

  • 모든 입력은 정수다.

  • 1 \le N \le 100 \ 000

  • 1 \le X_i \le 100 \ 000

  • 1 \le Y_i \le 100 \ 000

  • 0 \le R_i \le 10^{14}

  • 0 \le P_i \le 10^9


출력

각 i번째 줄에 i번 발전소가 가동되기 위한 최소 P_{init}을 출력한다.


예제 #1

1
1 1 10 5
10

예제 #2

2
1 1 7 5
2 2 20 10
7
15

1번 발전소는 모든 발전소에 7만큼 전력을 공급하면 가동된다.


2번 발전소는 모든 발전소에 15만큼 전력을 공급하면 가동된다. 왜냐하면 1번 발전소에 전력이 15만큼 공급된다면 1번 발전소가 가동되어서 5만큼 2번 발전소에 공급되고, 2번 발전소는 최종적으로 20만큼 공급이 되어서 가동되기 때문이다.


출처

eva
로그인해야 코드를 작성할 수 있어요.