Submission #1201891

#TimeUsernameProblemLanguageResultExecution timeMemory
1201891uranium235Hacker (BOI15_hac)Java
0 / 100
43 ms10340 KiB
//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)) deque.pollFirst(); best = Math.max(best, pref[deque.getFirst()]); } System.out.println(best); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...