| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1314035 | toyotacorolla86 | Feast (NOI19_feast) | Java | 0 ms | 0 KiB |
// Source: https://usaco.guide/general/io
import java.io.*;
import java.util.*;
public class Solution {
static int n, k;
static long[] a;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
a = new long[n];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < n; i++)
a[i] = Long.parseLong(st.nextToken());
long low = 0;
long high = 300000000000000L;
long ans = 0;
while(low <= high) {
long mid = low + (high - low) / 2;
long[] res = solve(mid);
if(res[1] <= k) {
ans = res[0] + mid * k;
high = mid - 1;
}
else
low = mid + 1;
}
System.out.println(ans);
}
private static long[] solve(long n) {
long dp0 = 0;
int c0 = 0;
long dp1 = -1000000000000000000L;
int c1 = 0;
for(long x : a) {
long next_dp0;
int next_c0;
if(dp0 > dp1) {
next_dp0 = dp0;
next_c0 = c0;
}
else if (dp1 > dp0) {
next_dp0 = dp1;
next_c0 = c1;
}
else {
next_dp0 = dp0;
next_c0 = Math.min(c0, c1);
}
long extend_val = dp1 + x;
long start_val = dp0 + x - n;
long next_dp1;
int next_c1;
if(extend_val > start_val) {
next_dp1 = extend_val;
next_c1 = c1;
}
else if (start_val > extend_val) {
next_dp1 = start_val;
next_c1 = c0 + 1;
}
else {
next_dp1 = extend_val;
next_c1 = Math.min(c1, c0 + 1);
}
dp0 = next_dp0;
c0 = next_c0;
dp1 = next_dp1;
c1 = next_c1;
}
if(dp0 > dp1) return new long[]{dp0, c0};
if(dp1 > dp0) return new long[]{dp1, c1};
return new long[]{dp0, Math.min(c0, c1)};
}
}