Submission #240499

#	Time	Username	Problem	Language	Result	Execution time	Memory
240499		conankun	Split the sequence (APIO14_sequence)	Java	60 / 100	790 ms	131072 KiB

sequence

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 int[201][100001];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    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];
        }
        br.close();
        solve();
    }
    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;
            }
        }
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        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]+" ");
        }
      	bw.flush();
        bw.close();
    }
}

• Subtask 1: 0 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 0 / 29