| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 240496 | conankun | 수열 (APIO14_sequence) | Java | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
import java.io.*;
import java.util.*;
public class sequence {
static int N,K;
static long S[] = new long[100001];
static long D[][] = new long[2][100001];
static int OPT[][] = new char[201][100001];
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException {
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
for(int i = 1 ; i <= N ; i++) {
S[i] = Integer.parseInt(st.nextToken());
S[i] += S[i-1];
}
solve();
br.close();
bw.flush();
bw.close();
}
private static boolean canSkip(int k, int i, int j,int threshold) {
return (D[(k-1)%2][i] - D[(k-1)%2][j] + S[N] * (S[j] - S[i]))
<= threshold * (S[j] - S[i]);
}
private static boolean canRemoveLastCandidate(int k, int i, int j, int l) {
return (D[(k-1)%2][i] - D[(k-1)%2][j] + S[N] * (S[j] - S[i])) * (S[l] - S[j])
<= (D[(k-1)%2][j] - D[(k-1)%2][l] + S[N] * (S[l] - S[j])) * (S[j] - S[i]);
}
private static void dp(int k) {
int [] candid = new int[N];
int front = 0, back = 0;
candid[back++] = k -1;
for(int i = k ; i <= N ; i++) {
while (back - front > 1 && canSkip(k, candid[front], candid[front + 1], (int) S[i])) {
front++;
}
int j = candid[front];
OPT[k][i] = j;
D[(k%2)][i] = D[(k-1)%2][j] + S[i] * S[j] - S[N] * S[j] + S[N] * S[i] - (S[i] * S[i]);
while (back - front > 1
&& canRemoveLastCandidate(k, i, candid[back-1], candid[back-2])) {
back--;
}
candid[back++]=i;
}
}
private static void solve() throws IOException {
for(int k = 1 ; k <= K ; k++) {
Arrays.fill(D[k%2], 0);
dp(k);
}
long ret = 0; int ind = 1;
for(int i = 1 ; i <= N ; i++) {
if(ret < D[K%2][i]) {
ret = D[K%2][i];
ind = i;
}
}
bw.write(ret+"\n");
int[] opt = new int[K];
int front = 0;
int k = K;
while (k > 0) {
opt[front++]=ind;
ind = OPT[k--][ind];
}
for(int i = K - 1; i >= 0; i--) {
bw.write(opt[i]+" ");
}
}
}