Codeforces Round 664 (Div. 1)

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
1394 Codeforces Round 664 (Div. 1) FINISHED False 7200 139937063 Aug. 12, 2020, 2:35 p.m.

Problems

Solved$
Index
Name
Type
Tags
Community Tag
Rating
( 1044 ) D Boboniu and Jianghu PROGRAMMING dp greedy sortings trees 2800

B"Since Boboniu finished building his Jianghu, he has been doing Kungfu on these mountains every day. Boboniu designs a map for his n mountains. He uses n-1 roads to connect all n mountains. Every pair of mountains is connected via roads. For the i -th mountain, Boboniu estimated the tiredness of doing Kungfu on the top of it as t_i . He also estimated the height of each mountain as h_i . A path is a sequence of mountains M such that for each i ( 1 <= i < |M| ), there exists a road between M_i and M_{i+1} . Boboniu would regard the path as a challenge if for each i ( 1 <= i<|M| ), h_{M_i} <= h_{M_{i+1}} . Boboniu wants to divide all n-1 roads into several challenges. Note that each road must appear in exactly one challenge, but a mountain may appear in several challenges. Boboniu wants to minimize the total tiredness to do all the challenges. The tiredness of a challenge M is the sum of tiredness of all mountains in it, i.e. sum_{i=1}^{|M|}t_{M_i} . He asked you to find the minimum total tiredness. As a reward for your work, you'll become a guardian in his Jianghu. The first line contains a single integer n ( 2 <= n <= 2 cdot 10^5 ), denoting the number of the mountains. The second line contains n integers t_1, t_2, ldots, t_n ( 1 <= t_i <= 10^6 ), denoting the tiredness for Boboniu to do Kungfu on each mountain. The third line contains n integers h_1, h_2, ldots, h_n ( 1 <= h_i <= 10^6 ), denoting the height of each mountain. Each of the following n - 1 lines contains two integers u_i , v_i ( 1 <= u_i, v_i <= n, u_i neq v_i ), denoting the ends of the road. It's guaranteed that all mountains are connected via roads. Print one integer: the smallest sum of tiredness of all challenges. For the first example: In the picture, the lighter a point is, the higher the mountain it represents. One o"...

Tutorials

Codeforces Round #664 Editorial

Submissions

Submission Id
Author(s)
Index
Submitted
Verdict
Language
Test Set
Tests Passed
Time taken (ms)
Memory Consumed (bytes)
Tags
Rating
90213523 ycx_girlfriend D Aug. 17, 2020, 9:27 a.m. OK D TESTS 100 358 54784000 2800
90072621 Tommy0103 D Aug. 16, 2020, 9:50 a.m. OK GNU C++11 TESTS 100 77 17612800 2800
90076538 Tommy0103 D Aug. 16, 2020, 11:05 a.m. OK GNU C++11 TESTS 100 93 17715200 2800
89838449 Vixbob D Aug. 14, 2020, 3:37 a.m. OK GNU C++11 TESTS 100 140 32768000 2800
89749302 xay5421 D Aug. 13, 2020, 12:01 a.m. OK GNU C++11 TESTS 100 140 57753600 2800
89781222 YLWang D Aug. 13, 2020, 9:43 a.m. OK GNU C++11 TESTS 100 155 43417600 2800
89717698 littlelittlehorse D Aug. 12, 2020, 4:12 p.m. OK GNU C++11 TESTS 100 171 14438400 2800
90452216 infinity37 D Aug. 20, 2020, 10:01 a.m. OK GNU C++11 TESTS 100 171 29491200 2800
89859481 Big_black_jujube D Aug. 14, 2020, 9:52 a.m. OK GNU C++11 TESTS 100 171 57548800 2800
90050028 npng D Aug. 16, 2020, 12:26 a.m. OK GNU C++11 TESTS 100 186 23552000 2800
89727485 Samsara_soul D Aug. 12, 2020, 4:34 p.m. OK GNU C++11 TESTS 100 186 23552000 2800
89838826 11235813213455 D Aug. 14, 2020, 3:49 a.m. OK GNU C++14 TESTS 100 139 45363200 2800
90740999 schtomi97 D Aug. 23, 2020, 9 a.m. OK GNU C++14 TESTS 100 249 23449600 2800
91120552 oipotato D Aug. 27, 2020, 9:33 a.m. OK GNU C++14 TESTS 100 249 30924800 2800
90200165 Qu0cNguyen D Aug. 17, 2020, 6:28 a.m. OK GNU C++14 TESTS 100 249 31436800 2800
89814596 xb0nS D Aug. 13, 2020, 4:54 p.m. OK GNU C++14 TESTS 100 249 36966400 2800
89753656 Sneakoscope D Aug. 13, 2020, 2:30 a.m. OK GNU C++14 TESTS 100 249 36966400 2800
89821919 lucaperju D Aug. 13, 2020, 6:49 p.m. OK GNU C++14 TESTS 100 264 30924800 2800
91516104 nan0S D Aug. 31, 2020, 6:06 p.m. OK GNU C++14 TESTS 100 264 31436800 2800
91039933 SoiMae D Aug. 26, 2020, 10:14 a.m. OK GNU C++14 TESTS 100 264 35225600 2800
90838947 Motarack D Aug. 24, 2020, 3:21 p.m. OK GNU C++14 TESTS 100 264 37785600 2800
90054559 ygy D Aug. 16, 2020, 3:38 a.m. OK GNU C++17 TESTS 100 109 33075200 2800
89760978 Akiha D Aug. 13, 2020, 5:02 a.m. OK GNU C++17 TESTS 100 234 29593600 2800
90054022 ygy D Aug. 16, 2020, 3:19 a.m. OK GNU C++17 TESTS 100 234 31436800 2800
89763437 Akiha D Aug. 13, 2020, 5:42 a.m. OK GNU C++17 TESTS 100 249 29593600 2800
90209423 xavier13540 D Aug. 17, 2020, 8:32 a.m. OK GNU C++17 TESTS 100 249 30924800 2800
90208731 xavier13540 D Aug. 17, 2020, 8:23 a.m. OK GNU C++17 TESTS 100 249 30924800 2800
91479418 penguin1017 D Aug. 31, 2020, 9:59 a.m. OK GNU C++17 TESTS 100 249 35123200 2800
89747920 AlexanderL D Aug. 12, 2020, 10:59 p.m. OK GNU C++17 TESTS 100 249 36966400 2800
90702875 Nakagawa.Kanon D Aug. 22, 2020, 4:17 p.m. OK GNU C++17 TESTS 100 249 40448000 2800
89860395 vipghn2003 D Aug. 14, 2020, 10:07 a.m. OK GNU C++17 TESTS 100 264 31436800 2800
89729637 QAQAutoMaton D Aug. 12, 2020, 5:35 p.m. OK GNU C++17 (64) TESTS 100 108 51097600 2800
89838932 11235813213455 D Aug. 14, 2020, 3:52 a.m. OK GNU C++17 (64) TESTS 100 124 53555200 2800
89719453 Egor D Aug. 12, 2020, 4:17 p.m. OK GNU C++17 (64) TESTS 100 124 65740800 2800
89713733 yosupo D Aug. 12, 2020, 4:02 p.m. OK GNU C++17 (64) TESTS 100 140 61747200 2800
91556537 dimas.kovas D Sept. 1, 2020, 10:30 a.m. OK GNU C++17 (64) TESTS 100 187 47513600 2800
89834165 emthrm D Aug. 14, 2020, 1:40 a.m. OK GNU C++17 (64) TESTS 100 202 60928000 2800
89809689 wwdd D Aug. 13, 2020, 3:50 p.m. OK GNU C++17 (64) TESTS 100 218 44851200 2800
89826628 David_Garcia D Aug. 13, 2020, 8:34 p.m. OK GNU C++17 (64) TESTS 100 218 54681600 2800
89739580 iaNTU D Aug. 12, 2020, 7:21 p.m. OK GNU C++17 (64) TESTS 100 218 56934400 2800
89749342 DmitryGrigorev D Aug. 13, 2020, 12:02 a.m. OK GNU C++17 (64) TESTS 100 218 64716800 2800
89731949 uwi D Aug. 12, 2020, 5:48 p.m. OK Java 11 TESTS 100 312 12390400 2800
91179497 Ahmad D Aug. 28, 2020, 4:49 a.m. OK Java 11 TESTS 100 592 147865600 2800
89782300 cwise D Aug. 13, 2020, 9:57 a.m. OK Java 11 TESTS 100 748 268390400 2800
91179966 PizzaLovers007 D Aug. 28, 2020, 5:01 a.m. OK Java 11 TESTS 100 826 268390400 2800
89824939 Taran_1407 D Aug. 13, 2020, 7:51 p.m. OK Java 8 TESTS 100 436 62464000 2800
89782212 cwise D Aug. 13, 2020, 9:56 a.m. OK Java 8 TESTS 100 498 133017600 2800
89825155 Taran_1407 D Aug. 13, 2020, 7:56 p.m. OK Java 8 TESTS 100 639 60825600 2800
89815379 nns2009 D Aug. 13, 2020, 5:05 p.m. OK MS C++ 2017 TESTS 100 655 37478400 2800
89832610 sansen D Aug. 14, 2020, 12:45 a.m. OK Rust TESTS 100 187 28160000 2800
90234600 xavier13540 D Aug. 17, 2020, 1:57 p.m. OK Rust TESTS 100 202 37273600 2800
90232702 xavier13540 D Aug. 17, 2020, 1:34 p.m. OK Rust TESTS 100 202 38195200 2800

remove filters

Back to search problems