Submission #653505

#	Time	Username	Problem	Language	Result	Execution time	Memory
653505		ziduo	Feast (NOI19_feast)	Java	41 / 100	1096 ms	90184 KiB

feast

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 = 1000000000000000L;
	    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
• Subtask 2: 0 / 8
• Subtask 3: 0 / 18
• Subtask 4: 10 / 10
• Subtask 5: 11 / 11
• Subtask 6: 20 / 20
• Subtask 7: 0 / 29