| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1344885 | primesparkz167 | Feast (NOI19_feast) | Java | 0 ms | 0 KiB |
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static StringTokenizer st;
public static int n;
public static int[] a;
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
n = nextInt();
int k = nextInt();
a = new int[n];
long hi = 0;
for (int i = 0; i < n; i++) {
int in = nextInt();
a[i] = in;
hi += Math.abs(in);
}
long lo = 0;
hi = hi << 1;//maybe double
while (lo < hi - 1) {
long mid = (lo + hi) >> 1;
long intv = solveL(mid)[1];
if (intv >= k) {
lo = mid;
} else {
hi = mid;
}
}
System.out.println((solveL(lo)[0] + k * lo));
}
public static long[] solveL(long l) {
long[][] dp = new long[n][2];
long[][] cnt = new long[n][2];
long[] ab;
dp[0][1] = a[0] - l;
cnt[0][1] = 1;
for (int i = 1; i < n; i++) {
ab = max(dp[i - 1][0], cnt[i - 1][0], dp[i - 1][1], cnt[i - 1][1]);
dp[i][0] = ab[0];
cnt[i][0] = ab[1];
ab = max(dp[i - 1][0] - l, cnt[i - 1][0] + 1, dp[i - 1][1], cnt[i - 1][1]);
dp[i][1] = ab[0] + a[i];
cnt[i][1] = ab[1];
}
return max(dp[n - 1][0], cnt[n - 1][0], dp[n - 1][1], cnt[n - 1][1]);
}
public static long[] max(long p10, long p11, long p20, long p21) {
long[] p1 = {p10, p11};
long[] p2 = {p20, p21};
return max(p1, p2);
}
public static long[] max(long[] p1, long[] p2) {
return (p1[0] == p2[0]) ? ((p1[1] >= p2[1]) ? p1 : p2) : ((p1[0] > p2[0]) ? p1 : p2);
}
public static int nextInt() {
return Integer.parseInt(next());
}
public static String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
}