문제지문 언어한국어expand_more한국어English길이 NNN의 두 정수 수열 AAA, BBB가 있다. 수열 AAA는 A1≥A2≥⋯≥ANA_1 \geq A_2 \geq \cdots \geq A_NA1≥A2≥⋯≥A을 만족한다. 1≤i,j≤N1 \leq i,j \leq N1≤i,j≤N에 대하여 Ci,j=Ai+BjC_{i,j}=A_i+B_jCi,j=Ai+Bj로 정의한다. 0≤Pj≤N0 \leq P_j \leq N0≤Pj≤N인 정수로 이루어진 길이 NNN의 수열 PPP를 고르려고 한다. PP는 ∑j=1NPj=K\sum_{j=1}^{N} P_j=Kj=1∑NPj=K 를 만족해야 한다. 다음 값의 최댓값을 구하여라. ∑j=1N∑i=1PjCi,j\sum_{j=1}^{N}\sum_{i=1}^{P_j} C_{i,j}j=1∑Ni=1∑P Pj=0P_j=0Pj=0이면 jjj번째 열에서는 아무 원소도 더하지 않는다.입력입력은 다음과 같은 형식으로 주어진다.TTT case1\mathrm{case}_1case1 case2\mathrm{case}_2case 출력각 테스트 케이스마다 가능한 값의 최댓값을 한 줄에 출력한다.제한 1≤T≤1 0001 \leq T \leq 1\,0001≤T≤1000 1≤N≤200 0001 \leq N \leq 200\,0001≤N≤200000 0≤K≤ 서브태스크#점수제한130N≤50N \leq 50N≤50이고, 모든 테스트 케이스에 대한 N2N^2N2의 합은 5 0005\,0005000 이하이다.270추가적인 제약이 없다.예제입력복사2 3 4 5 2 1 0 4 -1 2 0 3 1 7 8출력복사25 0태그 보기
