oj.uz

Submission #371398

# Submission time Handle Problem Language Result Execution time Memory
371398 2021-02-26T14:55:07 Z dapig Hacker (BOI15_hac) Java 11
0 / 100
 83 ms 8608 KB 
import java.io.*;
import java.util.*;

class hac {

	public static void main(String[] args) throws IOException {

		hac obj = new hac();

		obj.doStuff();

	}
	
	// first # is val, second is pos
	void add(ArrayDeque<int[]> q, int[] n) {
		while (!q.isEmpty() && q.peekLast()[0] >= n[0]) {
			q.pollLast();
		}
		q.addFirst(n);
	}

	int[] nums;
	int[] sums;
	private void doStuff() throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		nums = new int[Integer.parseInt(br.readLine())];
		sums = new int[nums.length];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < nums.length; i++) {
			nums[i] = Integer.parseInt(st.nextToken());
		}
		br.close();
		
		int cap = nums.length/2;
		if (nums.length%2==1) cap++;
		int rsum = 0;
		for (int i = 0; i < cap; i++) {
			rsum += nums[i];
		}
		for (int i = 0; i < nums.length; i++) {
			sums[i] = rsum;
			rsum -= nums[i];
			rsum += nums[(i+cap)%nums.length];
		}
		
		ArrayDeque<int[]> q = new ArrayDeque<>();
		int max = 0;
		for (int i = 0; i < cap; i++) {
			add(q, new int[] {sums[i], i});
		}
		for (int i = 0; i < nums.length; i++) {
			max = Math.max(max, q.peekLast()[0]);
			if (q.peekLast()[1] == i) q.pollLast();
			add(q, new int[] {sums[(i+cap)%nums.length], (i+cap)});
		}
		
		System.out.println(max);

	}

}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 8556 KB Output is correct
2 Incorrect 70 ms 8556 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 8556 KB Output is correct
2 Incorrect 70 ms 8556 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 8428 KB Output is correct
2 Incorrect 83 ms 8608 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 8556 KB Output is correct
2 Incorrect 70 ms 8556 KB Output isn't correct
3 Halted 0 ms 0 KB -