Codeforces Round 296 (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
527 Codeforces Round 296 (Div. 2) FINISHED False 7200 305212499 March 17, 2015, 4:45 p.m.

Problems

Solved$
Index
Name
Type
Tags
Community Tag
Rating
( 4803 ) D Clique Problem PROGRAMMING data structures dp greedy implementation sortings 2100

B"The clique problem is one of the most well-known NP-complete problems. Under some simplification it can be formulated as follows. Consider an undirected graph G. It is required to find a subset of vertices C of the maximum size such that any two of them are connected by an edge in graph G. Sounds simple, doesn't it? Nobody yet knows an algorithm that finds a solution to this problem in polynomial time of the size of the graph. However, as with many other NP-complete problems, the clique problem is easier if you consider a specific type of a graph. Consider n distinct points on a line. Let the i-th point have the coordinate xi and weight wi. Let's form graph G, whose vertices are these points and edges connect exactly the pairs of points (i, xe2 x80 x89j), such that the distance between them is not less than the sum of their weights, or more formally: |xi xe2 x80 x89- xe2 x80 x89xj| xe2 x80 x89 xe2 x89 xa5 xe2 x80 x89wi xe2 x80 x89+ xe2 x80 x89wj. Find the size of the maximum clique in such graph. The first line contains the integer n (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89n xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89200 xe2 x80 x89000) -- the number of points. Each of the next n lines contains two numbers xi, wi (0 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89xi xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89109, xe2 x80 x891 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89wi xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89109) -- the coordinate and the weight of a point. All xi are different. Print a single number -- the number of vertexes in the maximum clique of the given graph. If you happen to know how to solve this problem without using the specific properties of the graph formulated in the problem statement, then you are able to get a prize of one million dollars! The picture for the sample test."...

Tutorials

Codeforces Round #296 Editorial

Submissions

Submission Id
Author(s)
Index
Submitted
Verdict
Language
Test Set
Tests Passed
Time taken (ms)
Memory Consumed (bytes)
Tags
Rating
50226382 vjudge2 D Feb. 20, 2019, 7:30 a.m. OK Clang++17 Diagnostics TESTS 51 374 15155200 2100
10329363 AHTuTTuTyX D March 17, 2015, 8:17 p.m. OK Delphi TESTS 51 249 16076800 2100
11261889 ez_cjb D May 25, 2015, 8:03 a.m. OK FPC TESTS 51 93 2457600 2100
10525020 igdor99 D March 30, 2015, 1:35 p.m. OK FPC TESTS 51 93 3379200 2100
12241552 ThereIsNoSalvationForMe D July 27, 2015, 2:02 p.m. OK FPC TESTS 51 108 2457600 2100
43789779 luogu_bot1 D Oct. 4, 2018, 1:26 p.m. OK FPC TESTS 51 109 1638400 2100
19322486 tieuchanlong D July 22, 2016, 11:18 a.m. OK FPC TESTS 51 109 2048000 2100
10661519 moakhey D April 11, 2015, 11:08 p.m. OK FPC TESTS 51 109 3174400 2100
18452293 Gray_58 D June 14, 2016, 1:37 p.m. OK FPC TESTS 51 109 3788800 2100
57347514 luogu_bot5 D July 20, 2019, 12:56 a.m. OK FPC TESTS 51 124 1638400 2100
53892507 luogu_bot3 D May 9, 2019, 2:07 a.m. OK FPC TESTS 51 124 1638400 2100
44428525 luogu_bot2 D Oct. 17, 2018, 6:17 a.m. OK FPC TESTS 51 124 1638400 2100
10997037 stanleyuan D May 4, 2015, 3:03 p.m. OK GNU C TESTS 51 93 1638400 2100
10410424 meikoNiMaBi D March 23, 2015, 1:03 p.m. OK GNU C++ TESTS 51 46 1638400 2100
13547621 unknown_shadow D Oct. 11, 2015, 3:17 p.m. OK GNU C++ TESTS 51 46 1740800 2100
40986834 ReaLNero1 D July 30, 2018, 8:47 p.m. OK GNU C++ TESTS 51 46 3072000 2100
13854228 vjudge4 D Oct. 25, 2015, 1:42 p.m. OK GNU C++ TESTS 51 46 3174400 2100
10345018 wxjlzbcd D March 19, 2015, 4:53 a.m. OK GNU C++ TESTS 51 46 3584000 2100
22162603 zhan8855 D Nov. 11, 2016, 12:36 p.m. OK GNU C++ TESTS 51 46 4608000 2100
12638883 wxjlzbcd D Aug. 22, 2015, 8:22 a.m. OK GNU C++ TESTS 51 46 79974400 2100
10349892 whn6325689 D March 19, 2015, 2:37 p.m. OK GNU C++ TESTS 51 61 1638400 2100
40409217 vjudge2 D July 16, 2018, 11:34 a.m. OK GNU C++ TESTS 51 62 1638400 2100
13585272 vjudge4 D Oct. 13, 2015, 1:15 a.m. OK GNU C++ TESTS 51 62 1638400 2100
10328714 filippoqua D March 17, 2015, 7:43 p.m. OK GNU C++0x TESTS 51 93 1433600 2100
10328349 kennethsnow D March 17, 2015, 7:30 p.m. OK GNU C++0x TESTS 51 93 1433600 2100
10350810 sunacm D March 19, 2015, 4:07 p.m. OK GNU C++0x TESTS 51 93 1638400 2100
10348783 icylatte D March 19, 2015, 12:44 p.m. OK GNU C++0x TESTS 51 93 1638400 2100
10344290 stareven D March 19, 2015, 1:49 a.m. OK GNU C++0x TESTS 51 93 1638400 2100
10335041 GiorgiKldiashvili D March 18, 2015, 9:37 a.m. OK GNU C++0x TESTS 51 93 1638400 2100
10334350 Wumpus D March 18, 2015, 8:29 a.m. OK GNU C++0x TESTS 51 93 1638400 2100
10330344 aleksandar.ljamzin D March 17, 2015, 10:03 p.m. OK GNU C++0x TESTS 51 93 1638400 2100
10329103 lemushumus D March 17, 2015, 8:01 p.m. OK GNU C++0x TESTS 51 93 1638400 2100
10328636 filippoqua D March 17, 2015, 7:40 p.m. OK GNU C++0x TESTS 51 93 1638400 2100
57463696 luogu_bot3 D July 21, 2019, 2:42 p.m. OK GNU C++11 TESTS 51 46 1433600 2100
52271729 Xu_Zhiyuan D April 3, 2019, 1:22 p.m. OK GNU C++11 TESTS 51 46 1433600 2100
51958533 Fubuki D March 29, 2019, 5:09 a.m. OK GNU C++11 TESTS 51 46 1433600 2100
51957149 luogu_bot4 D March 29, 2019, 3:35 a.m. OK GNU C++11 TESTS 51 46 1433600 2100
43668781 luogu_bot3 D Oct. 2, 2018, 2:40 a.m. OK GNU C++11 TESTS 51 46 1433600 2100
43614643 Re_xy D Sept. 30, 2018, 3:43 p.m. OK GNU C++11 TESTS 51 46 1433600 2100
62095632 luogu_bot2 D Oct. 8, 2019, 7:26 a.m. OK GNU C++11 TESTS 51 46 1638400 2100
61745932 Frame233 D Oct. 3, 2019, 12:19 a.m. OK GNU C++11 TESTS 51 46 1638400 2100
58498499 luogu_bot3 D Aug. 9, 2019, 1:13 p.m. OK GNU C++11 TESTS 51 46 1638400 2100
54518287 luogu_bot1 D May 23, 2019, 11:05 a.m. OK GNU C++11 TESTS 51 46 1638400 2100
51955034 Nostalgically D March 29, 2019, 1:09 a.m. OK GNU C++14 TESTS 51 46 7065600 2100
50045715 interestingLSY D Feb. 17, 2019, 5:46 a.m. OK GNU C++14 TESTS 51 62 4198400 2100
36658292 q234rty D March 27, 2018, 4:59 a.m. OK GNU C++14 TESTS 51 62 16076800 2100
47375382 kataki D Dec. 22, 2018, 4:56 p.m. OK GNU C++14 TESTS 51 109 1638400 2100
40515674 RUSH_D_CAT D July 18, 2018, 1:13 p.m. OK GNU C++14 TESTS 51 109 1638400 2100
31709801 pikmike D Oct. 25, 2017, 12:58 p.m. OK GNU C++14 TESTS 51 109 1638400 2100
27689455 rawatds D June 9, 2017, 12:59 p.m. OK GNU C++14 TESTS 51 109 2457600 2100
47900935 trungttt D Jan. 4, 2019, 2:05 p.m. OK GNU C++14 TESTS 51 109 3174400 2100
24619402 rawr D Feb. 13, 2017, 1:42 a.m. OK GNU C++14 TESTS 51 109 3481600 2100
28251939 after D July 3, 2017, 10:14 a.m. OK GNU C++14 TESTS 51 109 5120000 2100
57642869 ST_C D July 24, 2019, 1:12 p.m. OK GNU C++17 TESTS 51 109 1638400 2100
48668764 cielavenir D Jan. 21, 2019, 9:29 a.m. OK GNU C++17 TESTS 51 109 1843200 2100
48581684 vjudge2 D Jan. 19, 2019, 4:56 p.m. OK GNU C++17 TESTS 51 109 1843200 2100
50223840 vjudge1 D Feb. 20, 2019, 6:24 a.m. OK GNU C++17 TESTS 51 109 3174400 2100
56787922 Excogitatoris D July 10, 2019, 9:14 a.m. OK GNU C++17 TESTS 51 109 3584000 2100
59583275 LeoRiether D Aug. 27, 2019, 4:55 p.m. OK GNU C++17 TESTS 51 124 1638400 2100
55417650 aceeca1 D June 11, 2019, 3:56 a.m. OK GNU C++17 TESTS 51 124 1638400 2100
55104458 khaled.farouk_2 D June 5, 2019, 12:31 a.m. OK GNU C++17 TESTS 51 124 1638400 2100
50070769 vjudge2 D Feb. 17, 2019, 5:35 p.m. OK GNU C++17 TESTS 51 124 1638400 2100
40701797 LazyGirl_HlqY D July 24, 2018, 11:19 a.m. OK GNU C++17 TESTS 51 124 1638400 2100
11125238 sultan.of.swing D May 17, 2015, 10:49 a.m. OK Java 7 TESTS 51 171 0 2100
11125117 sultan.of.swing D May 17, 2015, 10:34 a.m. OK Java 7 TESTS 51 171 0 2100
10334536 trunghieu11 D March 18, 2015, 8:48 a.m. OK Java 7 TESTS 51 217 0 2100
10494042 jlinge D March 27, 2015, 8:06 p.m. OK Java 7 TESTS 51 218 0 2100
10742485 LouisCK D April 16, 2015, 2:53 p.m. OK Java 7 TESTS 51 234 0 2100
10480643 maitony D March 27, 2015, 1:26 a.m. OK Java 7 TESTS 51 248 0 2100
10656285 simple95 D April 11, 2015, 9:34 a.m. OK Java 7 TESTS 51 249 0 2100
10407414 ishanktandon D March 23, 2015, 7:15 a.m. OK Java 7 TESTS 51 249 0 2100
10407357 LuuNhatPhi D March 23, 2015, 7:07 a.m. OK Java 7 TESTS 51 249 0 2100
10331257 edorundo D March 18, 2015, 1:04 a.m. OK Java 7 TESTS 51 249 0 2100
44891139 Srinivasa_Ramanujan D Oct. 26, 2018, 3:23 a.m. OK Java 8 TESTS 51 202 0 2100
31277172 coderbond007 D Oct. 13, 2017, 2:26 p.m. OK Java 8 TESTS 51 218 0 2100
40188062 prabhat236218 D July 11, 2018, 3:51 a.m. OK Java 8 TESTS 51 233 42496000 2100
23998385 rahulkhairwar D Jan. 20, 2017, 8:42 p.m. OK Java 8 TESTS 51 249 20582400 2100
10771505 dumak D April 18, 2015, 6:26 p.m. OK Java 8 TESTS 51 264 28672000 2100
25876645 MDL D March 28, 2017, 2:50 p.m. OK Java 8 TESTS 51 265 27852800 2100
12259969 upsolving D July 29, 2015, 6:06 a.m. OK Java 8 TESTS 51 280 0 2100
10656301 simple95 D April 11, 2015, 9:35 a.m. OK Java 8 TESTS 51 280 0 2100
10450117 .tx D March 25, 2015, 4:09 p.m. OK Java 8 TESTS 51 280 0 2100
10450111 lydxlx D March 25, 2015, 4:08 p.m. OK Java 8 TESTS 51 280 0 2100
10902796 og.kostya D April 27, 2015, 5:59 a.m. OK MS C# TESTS 51 140 13516800 2100
10329901 mircea85 D March 17, 2015, 9:09 p.m. OK MS C# TESTS 51 265 10752000 2100
10333927 azukun D March 18, 2015, 7:45 a.m. OK MS C# TESTS 51 358 16384000 2100
20651967 sunmoyi D Sept. 16, 2016, 3:41 a.m. OK MS C++ TESTS 51 93 1638400 2100
10351990 guitarist D March 19, 2015, 5:47 p.m. OK MS C++ TESTS 51 93 1638400 2100
10338946 superwatermelon D March 18, 2015, 2:33 p.m. OK MS C++ TESTS 51 93 1638400 2100
10438956 xiaoyu20123 D March 25, 2015, 12:49 p.m. OK MS C++ TESTS 51 93 2457600 2100
12410941 ALEXKIRNAS D Aug. 8, 2015, 7:20 a.m. OK MS C++ TESTS 51 93 3174400 2100
11078519 vjudge2 D May 12, 2015, 1:13 p.m. OK MS C++ TESTS 51 93 3174400 2100
10454319 pppgod D March 26, 2015, 6:06 a.m. OK MS C++ TESTS 51 93 3276800 2100
10440046 hakgb11 D March 25, 2015, 1:27 p.m. OK MS C++ TESTS 51 93 3276800 2100
10425813 kesakiyo D March 24, 2015, 6:08 p.m. OK MS C++ TESTS 51 93 3276800 2100
26785307 Leibniz_Zhang D May 1, 2017, 12:24 p.m. OK MS C++ TESTS 51 93 3686400 2100
61614191 CtrlAlt D Oct. 1, 2019, 2:38 p.m. OK MS C++ 2017 TESTS 51 405 1638400 2100
63062695 yorky D Oct. 21, 2019, 9:23 a.m. OK MS C++ 2017 TESTS 51 421 7987200 2100
44495603 hongquanntct D Oct. 18, 2018, 4:37 p.m. OK PHP TESTS 51 608 29388800 2100
44495512 hongquanntct D Oct. 18, 2018, 4:35 p.m. OK PHP TESTS 51 670 29388800 2100
44516084 hongquanntct D Oct. 18, 2018, 6:24 p.m. OK PHP TESTS 51 1138 77721600 2100
44515656 hongquanntct D Oct. 18, 2018, 6:20 p.m. OK PHP TESTS 51 1154 77721600 2100
10411546 robots.txt D March 23, 2015, 2:48 p.m. OK PyPy 2 TESTS 51 1154 18124800 2100
10339172 daniil_m D March 18, 2015, 2:54 p.m. OK PyPy 3 TESTS 51 1528 97382400 2100
10641621 user729 D April 9, 2015, 3:37 p.m. OK Python 2 TESTS 51 857 16076800 2100
11857263 allanyin D June 30, 2015, 3:33 p.m. OK Python 2 TESTS 51 873 16076800 2100
10569828 chiehmin D April 4, 2015, 6 a.m. OK Python 2 TESTS 51 888 16076800 2100
10624198 nealzane D April 7, 2015, 6:22 p.m. OK Python 2 TESTS 51 919 36761600 2100
12811884 chaosagent D Sept. 2, 2015, 7:34 a.m. OK Python 2 TESTS 51 920 24268800 2100
35900364 ______n______ D March 3, 2018, 7:25 p.m. OK Python 2 TESTS 51 920 41574400 2100
35884926 _____k_____ D March 3, 2018, 1:20 p.m. OK Python 2 TESTS 51 920 41574400 2100
35884662 _____i_____ D March 3, 2018, 1:15 p.m. OK Python 2 TESTS 51 920 41574400 2100
35874117 ______h______ D March 3, 2018, 7:45 a.m. OK Python 2 TESTS 51 920 41574400 2100
35873873 ______k______ D March 3, 2018, 7:40 a.m. OK Python 2 TESTS 51 920 41574400 2100
10491175 rpy3cpp D March 27, 2015, 3:13 p.m. OK Python 3 TESTS 51 857 18636800 2100
10724697 hydrotoast D April 14, 2015, 10:57 p.m. OK Python 3 TESTS 51 982 25190400 2100
10413058 robots.txt D March 23, 2015, 5:40 p.m. OK Python 3 TESTS 51 1013 41062400 2100
10479003 antonydeepak D March 26, 2015, 8:57 p.m. OK Python 3 TESTS 51 1060 24576000 2100
10350773 duckladydinh D March 19, 2015, 4:04 p.m. OK Python 3 TESTS 51 1091 18432000 2100
37868467 DevilJin D May 3, 2018, 5:08 p.m. OK Python 3 TESTS 51 1138 35737600 2100
10491076 rpy3cpp D March 27, 2015, 3:06 p.m. OK Python 3 TESTS 51 1200 28876800 2100
10352012 qhpeklh5599 D March 19, 2015, 5:49 p.m. OK Python 3 TESTS 51 1201 18329600 2100
16202615 surokpro D Feb. 19, 2016, 2:44 p.m. OK Python 3 TESTS 51 1450 21401600 2100
10656495 ttbxxls D April 11, 2015, 9:59 a.m. OK Python 3 TESTS 51 1465 27033600 2100
20167712 chiehmin D Aug. 26, 2016, 4:21 a.m. OK Ruby TESTS 51 1481 35635200 2100
10645059 ronaflx D April 10, 2015, 2:09 a.m. OK Scala TESTS 51 779 102400 2100

remove filters

Back to search problems