| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 240485 | conankun | Split the sequence (APIO14_sequence) | Java | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
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 char 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) {
List<Integer> candid = new ArrayList<>();
candid.addLast(k-1);
for(int i = k ; i <= N ; i++) {
while (candid.size() > 1 && canSkip(k, candid.get(0), candid.get(1), (int) S[i])) {
candid.remove(0);
}
int j = candid.get(0);
OPT[k][i] = (char) 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 (candid.size() > 1
&& canRemoveLastCandidate(k, i, candid.get(candid.size() - 1), candid.get(candid.size()-2))) {
candid.remove(candid.size() - 1);
}
candid.add(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");
char[] opt = new char[K];
int front = 0;
int k = K;
while (k > 0) {
opt[front++]=(char)ind;
ind = OPT[k--][ind];
}
for(int i = K - 1; i >= 0; i--) {
int x = opt[i];
bw.write(x+" ");
}
}
}