CostOfDancing
SRM 624 · 2013-12-22 · by MDantas
SRM 624 · 2013-12-22 · by MDantas · Graph Theory, Greedy, Sorting
Problem Statement
Problem Statement
Gustavo studies at the Byteversity (one of the best universities in Byteland). He's also very keen on dancing, so he decided to enroll at a dance school.
The school offers many different courses, each teaching one dance. Different courses may have different costs. You are given a
Gustavo would like to learn exactly K of those dances. He is a poor student, so his only priority is to pay as little as possible for the courses.
You are given the
Constraints
- danceCost will contain between 1 and 1,000 elements, inclusive.
- Each element of danceCost will be between 1 and 1,000, inclusive.
- K will be between 1 and the number of elements in danceCost, inclusive.
Examples
0)
2
{1, 5, 3, 4}
Returns: 4
Gustavo must pay for exactly two out of the four given courses. The cheapest possibility is to pay 1 for one course and then 3 for another course. The total cost is 1+3 = 4.
1)
3
{1, 5, 4}
Returns: 10
Gustavo has no choice here. He has to pay for all three courses, which costs 1+5+4 = 10.
2)
1
{2, 2, 4, 5, 3}
Returns: 2
Among all 5 possible courses he can take, the cheapest one is either the course #0 or course #1 (0-based).
3)
32
{118, 462, 735, 484, 643, 811, 847, 527, 655, 593, 611, 224, 923, 375, 710, 278, 392, 796, 585, 362, 504, 506, 939, 1000, 379, 155, 681, 319, 741, 543, 958, 858, 356, 692, 341, 351, 855, 539, 877, 509, 484, 840, 732, 406, 566, 794, 683, 957, 589, 619, 670, 444, 477, 608, 443, 207, 115, 123, 526, 855, 18, 835, 712, 373, 526, 404, 723, 380, 294, 952, 889, 777, 143, 972, 183, 708, 765, 217, 17, 705, 188, 686, 148, 16, 646, 943, 574, 760, 65, 451, 614, 434, 285, 677, 807, 811, 80, 881, 190, 373, 184, 430, 502, 326, 402, 684, 386, 166, 252, 402, 223, 791, 87, 370, 806, 84, 312, 732, 843, 729, 182, 456, 162, 467, 132, 320, 277, 563, 553, 818, 288, 736, 248, 789, 414, 649, 824, 799, 166, 75, 200, 388, 218, 638, 758, 375, 722, 421, 106, 564, 149, 288, 372, 311, 754, 855, 982, 30, 770, 534, 847, 57, 270, 446, 845, 683, 94, 668, 833, 612, 94, 32, 999, 311, 669, 108, 38, 742, 881, 143, 658, 29, 430, 381, 691, 183, 587, 673, 564, 356, 206, 763, 412, 827, 208, 608, 861, 654, 275, 693, 265, 721, 724, 615, 383, 745, 723, 420, 838, 603, 563, 495, 983, 992, 875, 26, 527, 462, 698, 442, 169, 255, 204, 581, 434, 412, 188, 294, 65, 815, 339, 681, 535, 414, 295, 269, 510, 17, 689, 348, 971, 251, 194, 306, 594, 69, 331, 120, 882, 380, 562, 50, 986, 117, 982, 419, 880, 522, 65, 944, 688, 403, 976, 222, 816, 271, 842, 326, 639, 530, 25, 962, 780, 218, 267, 726, 638, 597, 197, 871, 328, 110, 273, 313, 227, 254, 732, 106, 127, 148, 402, 814, 550, 377, 387, 717, 999, 229, 394, 638, 758, 418, 951, 890, 988, 217, 967, 625, 165, 163, 496, 492, 625, 768, 156, 851, 373, 887, 308, 852, 386, 61, 665, 935, 790, 404, 4, 788, 632, 397, 777, 741, 167, 727, 982, 154, 295, 948, 130, 459, 463, 625, 302, 87, 744, 458, 289, 469, 696, 596, 320, 82, 657, 336, 368, 798, 739, 371, 585, 722, 768, 714, 815, 934, 440, 796, 439, 735, 96, 568, 545, 558, 545, 847, 644, 640, 304, 932, 108, 351, 879, 779, 432, 887, 467, 800, 684, 557, 170, 621, 279, 289, 334, 93, 574, 125, 240, 364, 211, 335, 932, 756, 244, 476, 954, 239, 115, 609, 522, 575, 959, 401, 705, 743, 287, 171, 894, 323, 728, 63, 943, 358, 704, 628, 802, 629, 752, 393, 993, 963, 728, 924, 70, 971, 751, 23, 562, 217, 631, 83, 143, 941, 483, 848, 683, 122, 370, 576, 444, 449, 991, 738, 806, 46, 365, 959, 674, 116, 352, 666, 430, 431, 941, 851, 753, 43, 873, 314, 260, 855, 397, 402, 148, 879, 601, 182, 352, 971, 758, 147, 419, 100, 884, 577, 497, 248, 535, 170, 716, 238, 188, 497, 668, 128, 348, 421, 523, 572, 734, 782, 779, 130, 535, 926, 361, 488, 107, 712, 810, 216, 859, 228, 667, 94, 156, 163, 694, 43, 333, 409, 280, 872, 257, 948, 351, 604, 720, 873, 528, 453, 6, 306, 583, 893, 583, 295, 380, 41, 358, 189, 609, 216, 768, 275, 662, 924, 438, 355, 318, 122, 115, 949, 345, 371, 248, 695, 327, 967, 568, 854, 420, 925, 511, 354, 817, 445, 648, 196, 485, 5, 384, 93, 573, 504, 720, 234, 779, 509, 940, 96, 982, 54, 44, 326, 424, 644, 20, 750, 610, 939, 955, 29, 864, 817, 734, 680, 261, 733, 228, 746, 90, 963, 190, 662, 466, 261, 247, 244, 769, 538, 691, 750, 591, 87, 427, 14, 730, 447, 116, 691, 737, 422, 72, 600, 239, 805, 632, 499, 538, 211, 596, 979, 173, 138, 992, 639, 398, 238, 234, 519, 775, 277, 268, 717, 363, 695, 82, 444, 493, 197, 134, 229, 619, 205, 181, 857, 362, 164, 355, 899, 374, 303, 229, 546, 440, 220, 536, 837, 809, 122, 355, 935, 398, 975, 651, 112, 21, 732, 555, 513, 281, 40, 93, 899, 245, 273, 107, 606, 436, 813, 856, 161, 115, 84, 707, 554, 303, 594, 743, 111, 715, 449, 45, 464, 423, 47, 575, 443, 778, 481, 307, 58, 521, 400, 308, 117, 24, 766, 74, 812, 579, 929, 972, 45, 364, 30, 951, 18, 976, 693, 480, 42, 493, 876, 506, 916, 922, 432, 710, 699, 913, 369, 109, 785, 120, 768, 253, 143, 534, 326, 306, 112, 606, 630, 508, 969, 11, 458, 986, 986, 502, 465, 28, 995, 692, 885, 262, 613, 316, 971, 663, 580, 339, 771, 716, 810, 539, 968, 953, 72, 293, 610, 535, 898, 239, 42, 218, 250, 852, 555, 587, 705, 371, 966, 699, 62, 850, 960, 674, 518, 283, 337, 449, 973, 107, 165, 783, 997, 484, 87, 420, 129, 696, 306, 378, 287, 700, 596, 888, 551, 150, 474, 255, 873, 440, 306, 934, 641, 265, 608, 158, 899, 944, 959, 872, 402, 475, 6, 751, 958, 92, 170, 438, 787, 476, 816, 425, 175, 763, 312, 77, 264, 786, 683, 136, 577, 988, 70, 569, 605, 677, 79, 503}
Returns: 827
4)
137
{726, 725, 511, 731, 827, 820, 822, 997, 610, 961, 824, 425, 737, 350, 539, 49, 426, 802, 186, 108, 938, 114, 448, 7, 682, 52, 35, 760, 554, 358, 796, 632, 434, 658, 362, 261, 830, 536, 609, 439, 848, 784, 863, 584, 133, 753, 984, 910, 554, 169, 369, 491, 634, 816, 849, 316, 867, 883, 427, 773, 592, 223, 404, 26, 232, 117, 638, 61, 652, 246, 851, 851, 29, 65, 435, 513, 817, 770, 422, 371, 939, 142, 861, 924, 958, 62, 239, 176, 296, 666, 300, 888, 240, 703, 265, 823, 172, 902, 884, 175, 499, 734, 26, 879, 799, 812, 391, 615, 581, 164, 337, 871, 305, 198, 795, 614, 611, 385, 790, 906, 402, 441, 793, 641, 496, 409, 464, 667, 310, 699, 841, 160, 784, 218, 38, 934, 29, 780, 901, 962, 295, 237, 184, 952, 786, 978, 565, 396, 715, 706, 302, 116, 147, 446, 109, 642, 855, 924, 308, 516, 622, 500, 676, 757, 718, 65, 43, 98, 197, 943, 59, 491, 531, 243, 442, 669, 572, 359, 416, 638, 64, 69, 754, 562, 867, 214, 203, 721, 137, 862, 588, 110, 714, 615, 866, 431, 680, 260, 880, 228, 554, 939, 718, 85, 533, 512, 105, 456, 870, 520, 94, 285, 941, 199, 847, 807, 412, 401, 527, 548, 263, 466, 657, 328, 81, 874, 110, 760, 134, 989, 339, 687, 279, 56, 123, 163, 919, 227, 619, 788, 99, 64, 73, 39, 262, 271, 197, 25, 671, 75, 572, 285, 540, 580, 612, 620, 805, 721, 731, 938, 62, 69, 977, 340, 477, 99, 503, 395, 678, 473, 535, 128, 536, 959, 518, 149, 229, 714, 525, 899, 788, 96, 184, 679, 27, 795, 299, 831, 868, 29, 121, 929, 450, 97, 620, 926, 547, 474, 672, 224, 946, 206, 351, 833, 164, 868, 333, 392, 933, 857, 291, 720, 304, 826, 399, 330, 620, 49, 513, 839, 429, 633, 767, 878, 81, 739, 155, 627, 212, 827, 203, 158, 32, 905, 342, 196, 773, 675, 939, 705, 883, 581, 777, 187, 406, 527, 868, 26, 575, 380, 216, 355, 364, 983, 233, 796, 721, 387, 423, 284, 213, 977, 793, 597, 881, 135, 144, 653, 161, 82, 710, 43, 15, 838, 581, 420, 716, 449, 797, 642, 180, 13, 996, 544, 347, 580, 339, 419, 967, 113, 702, 531, 89, 495, 479, 970, 981, 622, 974, 141, 56, 35, 535, 70, 224, 116, 841, 939, 564, 638, 932, 743, 650, 928, 638, 348, 507, 329, 766, 825, 793, 467, 708, 882, 313, 186, 203, 293, 160, 528, 433, 567, 915, 320, 988, 490, 435, 828, 781, 350, 817, 712, 444, 818, 639, 82, 165, 498, 762, 930, 674, 554, 749, 381, 787, 61, 919, 341, 354, 78, 221, 138, 996, 135, 457, 983, 976, 891, 162, 756, 592, 979, 468, 36, 796, 458, 117, 961, 307, 230, 242, 981, 783, 990, 713, 922, 403, 631, 262, 756, 708, 834, 245, 55, 968, 54, 37, 296, 944, 551, 51, 536, 529, 870, 923, 676, 680, 39, 988, 986, 620, 230, 318, 402, 571, 31, 675, 973, 661, 937, 80, 721, 770, 325, 775, 90, 378, 164, 737, 673, 714, 787, 560, 594, 657, 482, 269, 336, 872, 257, 673, 491, 838, 991, 245, 408, 21, 919, 733, 681, 207, 812, 753, 329, 488, 528, 770, 865, 691, 506, 890, 756, 292, 801, 349, 300, 283, 969, 987, 506, 577, 12, 997, 414, 2, 593, 174, 374, 863, 906, 54, 70, 717, 807, 750, 205, 686, 519, 421, 728, 24, 310, 483, 667, 111, 831, 319, 745, 799, 657, 250, 376, 668, 598, 141, 669, 542, 314, 42, 405, 219, 448, 474, 288, 606, 223, 492, 291, 93, 264, 18, 468, 926, 852, 134, 388, 682, 804, 132, 832, 461, 733, 559, 128, 683, 700, 149, 224, 365, 190, 628, 584, 989, 453, 223, 594, 675, 714, 236, 119, 329, 605, 586, 254, 456, 720, 641, 489, 875, 124, 673, 335, 857, 231, 815, 891, 282, 963, 114, 647, 504, 742, 582, 493, 194, 804, 438, 221, 869, 26, 339, 197, 630, 925, 803, 438, 996, 795, 278, 222, 919, 302, 557, 127, 533, 371, 17, 166, 685, 482, 164, 188, 223, 745, 680, 769, 900, 118, 341, 768, 495, 31, 317, 476, 955, 471, 913, 302, 265, 543, 524, 535, 844, 432, 661, 728, 154, 29, 246, 838, 511, 409, 25, 85, 506, 57, 205, 405, 526, 545, 525, 20, 576, 193, 495, 882, 663, 760, 536, 927, 654, 411, 462, 497, 194, 474, 577, 347, 855, 822, 536, 365, 582, 912, 801, 87, 320, 6, 844, 845, 902, 368, 216, 829, 560, 711, 63, 222, 822, 950, 500, 475, 712, 313, 323, 905, 139, 251, 603, 993, 424, 490, 709, 6, 401, 509, 444, 73, 866, 287, 269, 120, 654, 485, 300, 565, 547, 714, 138, 368, 663, 990, 194, 374, 302, 516, 630, 792, 119, 232, 784, 542, 73, 492, 899, 826, 353, 343, 898, 570, 629, 166, 41, 635, 650, 341, 551, 196, 54, 689, 915, 69, 678, 460, 794, 331, 976, 424, 123, 446, 7, 258, 987, 80, 750, 886, 905, 454, 228, 154, 375, 208, 319, 416, 194, 321, 108, 745, 868, 513, 433, 135, 581, 462, 594, 727, 792, 921, 150, 266, 366, 508, 524, 353, 939, 625, 590, 195, 430, 169, 348, 804, 728, 19, 219, 922, 339, 326, 666, 558, 839, 450, 692, 771, 911, 286, 497, 54, 206, 998, 672, 572, 858, 195, 276, 796, 171, 217, 343, 600, 385, 42, 403, 112, 60, 974, 385, 750, 651, 50, 308, 841, 851, 351, 964, 761, 636, 812, 167, 194, 810, 838, 117, 19, 384, 744, 166, 554, 960, 508, 505, 696, 550, 259, 159, 961, 232, 544, 63, 235, 945, 722, 427, 796, 72, 390, 908, 60, 202, 426, 605, 363}
Returns: 10017
Submissions are judged against all 28 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class CostOfDancing with a public method int minimum(int K, vector<int> danceCost) · 28 test cases · 2 s / 256 MB per case