Educational Codeforces Round 108 (Rated for Div. 2)

Solutions are presented as using the least memory and the fastest execution time. It also takes the top 10 most recent solutions from each language. If you want to limit to a specific index, click the "Solved" button and go to that problem.

ContestId
Name
Phase
Frozen
Duration (Seconds)
Relative Time
Start Time
1519 Educational Codeforces Round 108 (Rated for Div. 2) FINISHED False 7200 117473063 April 29, 2021, 2:35 p.m.

Problems

Solved$
Index
Name
Type
Tags
Community Tag
Rating
( 15603 ) D Maximum Sum of Products PROGRAMMING brute force dp implementation math ternary search two pointers

B"You are given two integer arrays a and b of length n . You can reverse at most one subarray (continuous subsegment) of the array a . Your task is to reverse such a subarray that the sum sum limits_{i=1}^n a_i cdot b_i is maximized. The first line contains one integer n ( 1 <= n <= 5000 ). The second line contains n integers a_1, a_2, ... , a_n ( 1 <= a_i <= 10^7 ). The third line contains n integers b_1, b_2, ... , b_n ( 1 <= b_i <= 10^7 ). Print single integer -- maximum possible sum after reversing at most one subarray (continuous subsegment) of a . In the first example, you can reverse the subarray [4, 5] . Then a = [2, 3, 2, 3, 1] and 2 cdot 1 + 3 cdot 3 + 2 cdot 2 + 3 cdot 4 + 1 cdot 2 = 29 . In the second example, you don't need to use the reverse operation. 13 cdot 2 + 37 cdot 4 = 174 . In the third example, you can reverse the subarray [3, 5] . Then a = [1, 8, 3, 6, 7, 6] and 1 cdot 5 + 8 cdot 9 + 3 cdot 6 + 6 cdot 8 + 7 cdot 8 + 6 cdot 6 = 235 . "...

Tutorials

Educational Codeforces Round 108 Editorial

Submissions

No solutions yet.