이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*
* The order of the splits does not matter (figure this out by trying smaller cases).
* Use some algebra to transform the cost into a more workable form.
* ab + ac + bc = [(a + b + c)^2 - (a^2 + b^2 + c^2)] / 2
* (a + b + c) remains constant, so the goal is to find the best way to split the array into pieces a, b, c such that
* the sum of the squares is minimized. This can be done using dynamic programming, with a form of convex hull optimization.
* Runtime: O(NK)
*/
import java.util.*;
import java.io.*;
public class sequence {
final long INF = 5876543212345678L;
int N, K;
int[] arr;
int[][] from;
ConvexHull hull;
sequence(BufferedReader in, PrintWriter out) throws IOException {
StringTokenizer st = new StringTokenizer(in.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken()) + 1;
arr = new int[N];
st = new StringTokenizer(in.readLine());
for (int i = 0; i < N; i++) arr[i] = Integer.parseInt(st.nextToken());
hull = new ConvexHull();
from = new int[K + 1][N + 1];
long[][] dp = new long[2][N + 1];
Arrays.fill(dp[0], INF);
dp[0][0] = 0;
int currDP = 1;
for (int i = 1; i <= K; i++) {
hull.bot = 0;
hull.top = 0;
int currX = 0;
for (int j = 0; j <= N; j++) {
// Transition from best state
State s = hull.query(currX);
if (s == null) dp[currDP][j] = INF;
else {
dp[currDP][j] = s.eval(currX);
from[i][j] = s.i;
}
// Add new transition
if (dp[1-currDP][j] != INF) hull.add(new State(currX, dp[1-currDP][j], j));
// Move currX
if (j != N) currX += arr[j];
}
// System.out.println(Arrays.toString(dp[currDP]));
// System.out.println(Arrays.toString(from[i]));
currDP = 1 - currDP;
}
out.println(dp[1-currDP][N]);
int loc = N;
for (int i = K; i > 1; i--) {
loc = from[i][loc];
if (i != K) out.print(' ');
out.print(loc);
}
out.println();
}
class ConvexHull {
State[] states;
int bot, top;
ConvexHull() {
states = new State[N];
bot = 0;
top = 0;
}
void add(State s) {
// Remove states with the same sx
while (top - bot >= 2 && states[top-1].sx == s.sx) {
if (states[top-1].sy > s.sy) top--;
else return; // This state is useless
}
// Remove useless states
while (top - bot >= 2) {
State prev = states[top-1];
State prev2 = states[top-2];
if (prev2.intersect(prev) >= prev.intersect(s)) {
// prev is useless
top--;
} else break;
}
// Add this state
states[top++] = s;
}
/**
* Assumes x is in increasing order.
*/
State query(int x) {
// Remove outdated states
while (top - bot >= 2) {
if (states[bot].eval(x) >= states[bot+1].eval(x)) {
// Bottom state is outdated
bot++;
} else break;
}
if (top - bot == 0) return null;
return states[bot];
}
}
class State {
int sx, i;
long sy;
State(int sx, long sy, int i) {
this.sx = sx;
this.sy = sy;
this.i = i;
}
double intersect(State o) {
double part1 = (sy - o.sy) / (2 * (sx - o.sx));
double part2 = (sx + o.sx) / 2;
return part1 + part2;
}
long eval(int x) {
return sy + (long) (sx - x) * (sx - x);
}
}
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
new sequence(in, out);
in.close();
out.close();
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |