oj.uz

Submission #653504

# Submission time Handle Problem Language Result Execution time Memory
653504 2022-10-27T04:16:30 Z ziduo Feast (NOI19_feast) Java 11
0 / 100
 1000 ms 90188 KB 
import java.io.*;
import java.util.*;
public class feast {
	static int n;
	static int k;
	static long[][][] dp;
	static long[] A;
	public static void main(String[] args)throws IOException {
		// TODO Auto-generated method stub
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
	    StringTokenizer st = new StringTokenizer(br.readLine());
	    n = Integer.parseInt(st.nextToken());
	    k = Integer.parseInt(st.nextToken());
	    dp = new long[n+1][2][2];
	    dp[0][1][0] = -1000000000000000000L;
	    A = new long[n+1];
	    st = new StringTokenizer(br.readLine());
	    for(int i=1; i<=n; i++) 
	    	A[i] = Integer.parseInt(st.nextToken());
	    long l = 0;
	    long r = 1000000000;
	    while(l<r) {
	    	long m =(l+r)/2;
	    	if(solve(m))r = m;
	    	else l = m+1;
	    }
	    solve(l);
	    out.write(better(dp[n][0],dp[n][1])[0]+l*k+"\n");
	    out.flush();
	    out.close();
	}
	static boolean solve(long v) {
		for(int i=1; i<=n; i++) {
			dp[i][0] = better(dp[i-1][0], dp[i-1][1]);
			dp[i][1] = better(new long[]{dp[i-1][0][0]+A[i]-v, dp[i-1][0][1]+1},new long[]{dp[i-1][1][0]+A[i],dp[i-1][1][1]});
		}
		return better(dp[n][0], dp[n][1])[1]<=k;
	}
	static long[] better(long[] a, long[]b) {
		if(a[0]==b[0])return a[1]<b[1] ? a:b;
		return a[0] > b[0] ? a: b;
	}
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1093 ms 87040 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1082 ms 90188 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 86256 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 108 ms 9628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 108 ms 9628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 108 ms 9628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1093 ms 87040 KB Time limit exceeded
2 Halted 0 ms 0 KB -