제출 #602370

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
602370		ziduo	Hacker (BOI15_hac)	Java	100 / 100	365 ms	31612 KiB

hac

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.peekFirst()[0] >= n[0]) {
			q.pollFirst();
		}
		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]);
			//System.out.println(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: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 40 / 40