| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 371419 |
2021-02-26T15:19:42 Z |
dapig |
Hacker (BOI15_hac) |
Java 11 |
|
460 ms |
32204 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.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);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
73 ms |
8684 KB |
Output is correct |
| 2 |
Correct |
71 ms |
8556 KB |
Output is correct |
| 3 |
Correct |
71 ms |
8556 KB |
Output is correct |
| 4 |
Correct |
71 ms |
8556 KB |
Output is correct |
| 5 |
Correct |
75 ms |
8524 KB |
Output is correct |
| 6 |
Correct |
73 ms |
8556 KB |
Output is correct |
| 7 |
Correct |
82 ms |
8544 KB |
Output is correct |
| 8 |
Correct |
78 ms |
8428 KB |
Output is correct |
| 9 |
Correct |
75 ms |
8428 KB |
Output is correct |
| 10 |
Correct |
78 ms |
8556 KB |
Output is correct |
| 11 |
Correct |
76 ms |
8552 KB |
Output is correct |
| 12 |
Correct |
79 ms |
8300 KB |
Output is correct |
| 13 |
Correct |
73 ms |
8596 KB |
Output is correct |
| 14 |
Correct |
72 ms |
8556 KB |
Output is correct |
| 15 |
Correct |
72 ms |
8556 KB |
Output is correct |
| 16 |
Correct |
74 ms |
8556 KB |
Output is correct |
| 17 |
Correct |
82 ms |
8432 KB |
Output is correct |
| 18 |
Correct |
79 ms |
8684 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
73 ms |
8684 KB |
Output is correct |
| 2 |
Correct |
71 ms |
8556 KB |
Output is correct |
| 3 |
Correct |
71 ms |
8556 KB |
Output is correct |
| 4 |
Correct |
71 ms |
8556 KB |
Output is correct |
| 5 |
Correct |
75 ms |
8524 KB |
Output is correct |
| 6 |
Correct |
73 ms |
8556 KB |
Output is correct |
| 7 |
Correct |
82 ms |
8544 KB |
Output is correct |
| 8 |
Correct |
78 ms |
8428 KB |
Output is correct |
| 9 |
Correct |
75 ms |
8428 KB |
Output is correct |
| 10 |
Correct |
78 ms |
8556 KB |
Output is correct |
| 11 |
Correct |
76 ms |
8552 KB |
Output is correct |
| 12 |
Correct |
79 ms |
8300 KB |
Output is correct |
| 13 |
Correct |
73 ms |
8596 KB |
Output is correct |
| 14 |
Correct |
72 ms |
8556 KB |
Output is correct |
| 15 |
Correct |
72 ms |
8556 KB |
Output is correct |
| 16 |
Correct |
74 ms |
8556 KB |
Output is correct |
| 17 |
Correct |
82 ms |
8432 KB |
Output is correct |
| 18 |
Correct |
79 ms |
8684 KB |
Output is correct |
| 19 |
Correct |
80 ms |
8556 KB |
Output is correct |
| 20 |
Correct |
89 ms |
8576 KB |
Output is correct |
| 21 |
Correct |
93 ms |
8556 KB |
Output is correct |
| 22 |
Correct |
130 ms |
9692 KB |
Output is correct |
| 23 |
Correct |
214 ms |
12264 KB |
Output is correct |
| 24 |
Correct |
127 ms |
9568 KB |
Output is correct |
| 25 |
Correct |
217 ms |
12256 KB |
Output is correct |
| 26 |
Correct |
215 ms |
12364 KB |
Output is correct |
| 27 |
Correct |
70 ms |
8556 KB |
Output is correct |
| 28 |
Correct |
72 ms |
8556 KB |
Output is correct |
| 29 |
Correct |
75 ms |
8556 KB |
Output is correct |
| 30 |
Correct |
188 ms |
11944 KB |
Output is correct |
| 31 |
Correct |
187 ms |
11688 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
70 ms |
8556 KB |
Output is correct |
| 2 |
Correct |
85 ms |
8448 KB |
Output is correct |
| 3 |
Correct |
217 ms |
12420 KB |
Output is correct |
| 4 |
Correct |
329 ms |
15840 KB |
Output is correct |
| 5 |
Correct |
346 ms |
17636 KB |
Output is correct |
| 6 |
Correct |
353 ms |
21472 KB |
Output is correct |
| 7 |
Correct |
361 ms |
22756 KB |
Output is correct |
| 8 |
Correct |
408 ms |
30592 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
73 ms |
8684 KB |
Output is correct |
| 2 |
Correct |
71 ms |
8556 KB |
Output is correct |
| 3 |
Correct |
71 ms |
8556 KB |
Output is correct |
| 4 |
Correct |
71 ms |
8556 KB |
Output is correct |
| 5 |
Correct |
75 ms |
8524 KB |
Output is correct |
| 6 |
Correct |
73 ms |
8556 KB |
Output is correct |
| 7 |
Correct |
82 ms |
8544 KB |
Output is correct |
| 8 |
Correct |
78 ms |
8428 KB |
Output is correct |
| 9 |
Correct |
75 ms |
8428 KB |
Output is correct |
| 10 |
Correct |
78 ms |
8556 KB |
Output is correct |
| 11 |
Correct |
76 ms |
8552 KB |
Output is correct |
| 12 |
Correct |
79 ms |
8300 KB |
Output is correct |
| 13 |
Correct |
73 ms |
8596 KB |
Output is correct |
| 14 |
Correct |
72 ms |
8556 KB |
Output is correct |
| 15 |
Correct |
72 ms |
8556 KB |
Output is correct |
| 16 |
Correct |
74 ms |
8556 KB |
Output is correct |
| 17 |
Correct |
82 ms |
8432 KB |
Output is correct |
| 18 |
Correct |
79 ms |
8684 KB |
Output is correct |
| 19 |
Correct |
80 ms |
8556 KB |
Output is correct |
| 20 |
Correct |
89 ms |
8576 KB |
Output is correct |
| 21 |
Correct |
93 ms |
8556 KB |
Output is correct |
| 22 |
Correct |
130 ms |
9692 KB |
Output is correct |
| 23 |
Correct |
214 ms |
12264 KB |
Output is correct |
| 24 |
Correct |
127 ms |
9568 KB |
Output is correct |
| 25 |
Correct |
217 ms |
12256 KB |
Output is correct |
| 26 |
Correct |
215 ms |
12364 KB |
Output is correct |
| 27 |
Correct |
70 ms |
8556 KB |
Output is correct |
| 28 |
Correct |
72 ms |
8556 KB |
Output is correct |
| 29 |
Correct |
75 ms |
8556 KB |
Output is correct |
| 30 |
Correct |
188 ms |
11944 KB |
Output is correct |
| 31 |
Correct |
187 ms |
11688 KB |
Output is correct |
| 32 |
Correct |
70 ms |
8556 KB |
Output is correct |
| 33 |
Correct |
85 ms |
8448 KB |
Output is correct |
| 34 |
Correct |
217 ms |
12420 KB |
Output is correct |
| 35 |
Correct |
329 ms |
15840 KB |
Output is correct |
| 36 |
Correct |
346 ms |
17636 KB |
Output is correct |
| 37 |
Correct |
353 ms |
21472 KB |
Output is correct |
| 38 |
Correct |
361 ms |
22756 KB |
Output is correct |
| 39 |
Correct |
408 ms |
30592 KB |
Output is correct |
| 40 |
Correct |
262 ms |
12916 KB |
Output is correct |
| 41 |
Correct |
301 ms |
14136 KB |
Output is correct |
| 42 |
Correct |
333 ms |
14416 KB |
Output is correct |
| 43 |
Correct |
369 ms |
18016 KB |
Output is correct |
| 44 |
Correct |
431 ms |
30424 KB |
Output is correct |
| 45 |
Correct |
356 ms |
15912 KB |
Output is correct |
| 46 |
Correct |
366 ms |
22880 KB |
Output is correct |
| 47 |
Correct |
417 ms |
30648 KB |
Output is correct |
| 48 |
Correct |
372 ms |
31148 KB |
Output is correct |
| 49 |
Correct |
460 ms |
32204 KB |
Output is correct |
| 50 |
Correct |
457 ms |
32108 KB |
Output is correct |
