Submission #1201899

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201899		uranium235	Hacker (BOI15_hac)	Java	100 / 100	372 ms	73832 KiB

hac

//package ojuz;

import java.io.*;
import java.util.*;

public class hac {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(reader.readLine());
        int moves = (n + 1) / 2;
        int[] arr = new int[n + moves - 1];
        String[] read = reader.readLine().split(" ");
        for (int i = 0; i < n; i++) arr[i] = Integer.parseInt(read[i]);
        for (int i = n; i < arr.length; i++) arr[i] = arr[i - n];

        int val = 0;
        for (int i = 0; i < moves; i++) val += arr[i];

        int[] pref = new int[n + moves - 1];
        for (int i = 0; i < n - 1; i++) {
            pref[i] = val;
            val -= arr[i];
            val += arr[i + moves];
        }
        pref[n - 1] = val;
        for (int i = n; i < pref.length; i++) pref[i] = pref[i - n];

        Deque<Integer> deque = new ArrayDeque<>();
        for (int i = 0; i < moves; i++) {
            while (!deque.isEmpty() && pref[deque.getLast()] >= pref[i]) deque.pollLast();
            deque.addLast(i);
        }

        int best = pref[deque.getFirst()];
        for (int i = moves; i < pref.length; i++) {
            while (!deque.isEmpty() && pref[deque.getLast()] >= pref[i]) deque.pollLast();
            deque.addLast(i);
            if (deque.getFirst() < (i - moves + 1)) deque.pollFirst();
            best = Math.max(best, pref[deque.getFirst()]);
        }
        System.out.println(best);
    }
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 40 / 40