oj.uz

Submission #653505

# Submission time Handle Problem Language Result Execution time Memory
653505 2022-10-27T04:19:41 Z ziduo Feast (NOI19_feast) Java 11
41 / 100
 1000 ms 90184 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 = 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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1091 ms 84676 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 1096 ms 90184 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 1063 ms 86320 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 9500 KB Output is correct
2 Correct 106 ms 9928 KB Output is correct
3 Correct 104 ms 9544 KB Output is correct
4 Correct 102 ms 9768 KB Output is correct
5 Correct 104 ms 9840 KB Output is correct
6 Correct 110 ms 9476 KB Output is correct
7 Correct 105 ms 9912 KB Output is correct
8 Correct 108 ms 9632 KB Output is correct
9 Correct 100 ms 9904 KB Output is correct
10 Correct 100 ms 9684 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 9500 KB Output is correct
2 Correct 106 ms 9928 KB Output is correct
3 Correct 104 ms 9544 KB Output is correct
4 Correct 102 ms 9768 KB Output is correct
5 Correct 104 ms 9840 KB Output is correct
6 Correct 110 ms 9476 KB Output is correct
7 Correct 105 ms 9912 KB Output is correct
8 Correct 108 ms 9632 KB Output is correct
9 Correct 100 ms 9904 KB Output is correct
10 Correct 100 ms 9684 KB Output is correct
11 Correct 122 ms 12156 KB Output is correct
12 Correct 132 ms 11448 KB Output is correct
13 Correct 117 ms 11368 KB Output is correct
14 Correct 125 ms 11368 KB Output is correct
15 Correct 118 ms 11796 KB Output is correct
16 Correct 127 ms 11360 KB Output is correct
17 Correct 120 ms 11776 KB Output is correct
18 Correct 114 ms 11392 KB Output is correct
19 Correct 124 ms 11396 KB Output is correct
20 Correct 126 ms 12304 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 9500 KB Output is correct
2 Correct 106 ms 9928 KB Output is correct
3 Correct 104 ms 9544 KB Output is correct
4 Correct 102 ms 9768 KB Output is correct
5 Correct 104 ms 9840 KB Output is correct
6 Correct 110 ms 9476 KB Output is correct
7 Correct 105 ms 9912 KB Output is correct
8 Correct 108 ms 9632 KB Output is correct
9 Correct 100 ms 9904 KB Output is correct
10 Correct 100 ms 9684 KB Output is correct
11 Correct 122 ms 12156 KB Output is correct
12 Correct 132 ms 11448 KB Output is correct
13 Correct 117 ms 11368 KB Output is correct
14 Correct 125 ms 11368 KB Output is correct
15 Correct 118 ms 11796 KB Output is correct
16 Correct 127 ms 11360 KB Output is correct
17 Correct 120 ms 11776 KB Output is correct
18 Correct 114 ms 11392 KB Output is correct
19 Correct 124 ms 11396 KB Output is correct
20 Correct 126 ms 12304 KB Output is correct
21 Correct 220 ms 14908 KB Output is correct
22 Correct 234 ms 14444 KB Output is correct
23 Correct 234 ms 14660 KB Output is correct
24 Correct 205 ms 14724 KB Output is correct
25 Correct 223 ms 14484 KB Output is correct
26 Correct 235 ms 14796 KB Output is correct
27 Correct 213 ms 14628 KB Output is correct
28 Correct 216 ms 14896 KB Output is correct
29 Correct 220 ms 14408 KB Output is correct
30 Correct 219 ms 14636 KB Output is correct

Subtask #7
0 / 29.0

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