#P4868. [Shoi2017]期末考试
[Shoi2017]期末考试
[六省联考 2017] 期末考试
题目描述
有 位同学,每位同学都参加了全部的 门课程的期末考试,都在焦急的等待成绩的公布。
第 位同学希望在第 天或之前得知所有课程的成绩。如果在第 天,有至少一门课程的成绩没有公布,他就会等待最后公布成绩的课程公布成绩,每等待一天就会产生 不愉快度。
对于第 门课程,按照原本的计划,会在第 天公布成绩。
有如下两种操作可以调整公布成绩的时间:
- 将负责课程 的部分老师调整到课程 ,调整之后公布课程 成绩的时间推迟一天,公布课程 成绩的时间提前一天;每次操作产生 不愉快度。
- 增加一部分老师负责学科 ,这将导致学科 的出成绩时间提前一天;每次操作产生 不愉快度。
上面两种操作中的参数 均可任意指定,每种操作均可以执行多次,每次执行时都可以重新指定参数。
现在希望你通过合理的操作,使得最后总的不愉快度之和最小,输出最小的不愉快度之和即可。
输入格式
第一行三个非负整数 ,描述三种不愉快度。
第二行两个正整数 ,分别表示学生的数量和课程的数量,其中 。
第三行 个正整数 ,表示每个学生希望的公布成绩的时间。
第四行 个正整数 ,表示按照原本的计划,每门课程公布成绩的时间。
输出格式
输出一行一个整数,表示最小的不愉快度之和。
样例 #1
样例输入 #1
100 100 2
4 5
5 1 2 3
1 1 2 3 3
样例输出 #1
6
样例 #2
样例输入 #2
3 5 4
5 6
1 1 4 7 8
2 3 3 1 8 2
样例输出 #2
33
样例 #3
输入 #3
50 77 80
900 1000
1443 1130 490 191 698 1543 1149 1120 1734 1448 1585 323 1320 1292 855 937 35 1650 1591 1124 1312 401 1434 283 282 898 958 874 787 289 662 847 941 127 1960 1550 98 131 1933 14 1613 68 1284 1306 495 737 415 674 1691 1289 804 535 1529 835 1837 610 1047 936 905 349 1571 916 857 280 402 1000 1059 1254 1789 75 19 717 431 1748 1541 1274 792 1394 1148 603 1197 1812 958 451 1637 1601 1462 1481 1517 1746 17 601 773 1459 641 929 1649 982 1389 101 490 1807 95 1837 346 1433 532 242 1379 1087 944 1908 1513 1508 1256 918 1731 1308 1893 1600 1630 640 328 493 586 1294 1520 1883 1259 311 1973 925 857 1728 961 236 1312 1921 306 1314 1393 937 1738 909 1264 679 511 1026 1459 483 1131 1128 473 1619 844 409 1201 150 1829 628 543 1069 1212 1950 138 1116 378 1324 1217 1390 334 1738 481 575 10 1815 384 1295 1988 1831 998 69 247 16 1839 1738 1312 1965 1018 138 433 1310 1949 7 1585 1590 910 486 233 1676 1931 879 536 682 1683 145 1505 1025 427 1564 872 3 443 1253 793 1672 94 709 1729 858 277 1834 1282 744 1477 181 1300 1575 1124 187 126 140 800 1076 961 931 1608 1743 1438 1292 1185 476 1850 1800 610 656 577 1392 936 165 401 1247 1795 663 1786 1107 1223 824 1893 1792 796 1900 1914 1644 1263 1342 552 692 511 1994 81 118 1968 1697 1067 197 1707 1000 336 409 1836 392 1902 620 1299 544 1241 1565 1364 175 1428 1345 535 234 620 1533 248 1340 1389 1693 1720 929 1642 577 1226 506 1881 1738 71 1772 805 1362 299 496 619 1121 229 1909 1677 392 1355 1354 706 1578 356 1940 1412 1086 1788 1934 512 575 707 532 298 524 206 1047 246 1384 853 1484 848 667 227 365 21 1519 1178 566 8 595 1548 777 942 860 1939 1787 1522 1567 761 1844 1506 1337 945 1331 799 439 668 568 721 1086 277 1288 1249 196 1622 333 478 341 1392 1939 1641 191 135 380 1256 838 68 269 1030 385 1489 319 833 1595 1568 927 1547 1107 117 142 699 364 1447 465 1433 942 579 1490 773 1859 1097 1149 1392 362 429 1652 641 856 1671 1100 1633 434 756 1022 863 1845 770 1111 1982 1582 72 1320 706 770 1116 1142 1063 1591 123 27 58 265 1748 1347 909 1942 1069 128 1207 1362 1501 1831 594 1076 1136 737 876 1175 103 1451 102 1770 549 182 104 1 1667 1015 1627 1905 1308 280 1741 760 850 165 449 675 1223 1681 1596 1589 1397 1902 249 1095 679 1160 54 994 1117 1883 1893 391 1260 1720 476 312 1788 1653 1381 1452 616 1130 95 1727 593 1604 1787 1135 972 1461 1439 96 1951 194 1223 1113 808 404 1743 309 54 1128 586 83 1870 1263 1518 743 1511 1982 534 1750 1294 447 1247 1134 499 1007 603 1084 826 110 1281 547 12 178 1482 1148 899 548 422 1072 1489 1809 1365 1152 1242 1610 1343 1662 869 852 1869 225 1311 153 301 1173 199 1750 1329 312 1587 91 1841 735 1994 1470 276 831 265 1240 475 996 782 150 1447 1677 832 1401 494 365 1269 1463 298 1564 601 615 1529 757 206 1625 462 374 327 1740 190 1890 523 1126 949 1522 88 1808 415 704 1486 1351 1839 1850 384 92 1419 709 1143 293 1069 632 830 1674 1540 45 1895 856 177 115 244 1138 1115 590 1935 11 1467 1317 546 781 336 68 64 1301 1309 1416 1291 1876 1174 245 1083 160 1543 1427 1181 833 797 253 705 1812 1594 1217 60 412 693 306 100 172 1544 1449 1319 670 560 1776 500 1231 1953 1446 831 1808 2000 1918 1858 1591 535 79 999 796 52 1781 351 1404 522 879 494 1930 270 1231 236 681 1531 397 1605 1443 847 1764 586 69 1836 1860 478 1296 1672 1342 1466 1962 589 1771 922 1707 1913 1766 110 1073 895 1773 490 236 901 228 1382 466 692 1617 1502 1644 171 545 723 535 1388 722 1384 1269 350 119 1558 921 633 1064 632 1262 301 159 912 1137 603 379 464 18 714 737 2 1320 916 1590 1249 986 134 38 381 166 1091 736 443 1085 290 248 579 437 972 1124 1120 918 1327 880 404 414 173 122 705 893 317 950 976 1849 489 1338 30 1420 639 1667 410 1057 993 479 1017 586 229 1201 1954 1277 485 625 1027 66 943 281 1162 1863 1526 1241 524 700 367 451 401 519 1829 495 1558 578 566 377 346 184 1540 1630 769 1163 1301 1011 1636 1761 308 1022 1503 1666 1773 1195 1250 284 132 1464 1809 543 1647 1369 1460 1618 24 1765 311 1292 1420 1239 331 1083 430 1693 35 913 1956 1725 168 1650 1241 763 582 1655 250 1812 525 1086 1449 551 1184 1367 1341 1671
1385 200 384 1450 627 1803 528 1325 1023 1163 254 445 288 1994 1362 1631 495 622 277 1961 903 735 501 1079 1978 1291 261 1095 1738 995 778 893 1361 1595 1871 1296 746 1277 850 1883 213 951 484 1101 647 920 1917 1449 631 1271 1510 1943 371 1324 958 1521 249 1045 1078 823 1390 387 948 715 1402 154 676 1814 1786 949 1426 225 525 1759 1505 845 840 1770 1975 396 1186 92 479 1461 360 478 1749 1252 378 108 1998 247 828 279 317 1442 678 1846 1599 604 1029 1952 1632 592 1272 755 708 445 51 241 991 1574 431 1246 189 1715 168 35 1435 270 62 1694 1772 135 437 1472 1989 1 1093 381 384 1938 1162 623 1581 791 293 36 45 894 601 1084 438 234 447 1580 786 370 1314 317 1759 1762 1108 717 1504 392 1127 172 634 1912 1157 1473 648 89 1833 1235 1240 1350 1988 577 268 1486 249 1002 90 533 1136 949 1980 1569 1911 1899 1985 989 1900 568 202 665 1748 1646 254 200 1544 881 1174 416 1203 859 1137 1390 1045 1898 418 1951 163 1790 781 760 1188 28 1038 400 1525 1037 1425 1921 1286 1423 395 1498 300 1699 624 447 1709 957 1546 1031 1766 760 985 1165 904 79 509 337 551 1237 222 1748 1242 286 325 1311 1518 852 64 1292 35 1667 722 603 1693 1212 112 1839 1860 694 1269 1599 1188 1624 639 1909 1614 529 1984 1506 646 401 1437 1304 1027 637 1651 303 1729 542 1773 865 770 1570 719 1709 1913 426 1006 1447 958 667 1094 1591 1885 77 979 1254 1558 1775 856 1364 142 1009 523 1509 461 1752 566 1742 271 1629 760 1741 563 814 1682 255 1039 1756 539 1336 777 508 1389 1230 95 406 1829 350 1585 1977 1270 6 1185 1445 231 1609 1850 511 32 1087 1286 881 1169 1570 1591 567 1964 417 639 1650 358 1152 1639 1305 1050 567 1132 964 150 1199 637 1103 43 1928 1599 1325 897 1734 409 1314 1201 1999 1448 312 873 1438 1724 1835 492 692 1129 1965 159 1009 1927 211 1501 1519 291 117 180 1736 1484 1634 1958 1963 806 122 25 59 138 1266 1735 719 1716 628 1791 1332 724 1612 642 214 254 172 359 1019 1866 409 263 1864 932 1547 705 553 1181 1985 1848 686 1992 1675 2000 472 1902 1918 212 672 1467 260 1155 961 1662 1737 1486 1273 1469 159 1692 1004 1599 75 1559 1537 1376 1957 1949 1955 1088 1564 463 193 788 1696 1445 1150 1924 1334 1399 145 875 1640 566 1926 75 818 609 1788 998 918 1136 710 1622 569 1117 986 1813 1540 1190 276 6 531 1869 1844 874 329 840 524 556 1579 1537 435 230 688 1350 1268 1849 1272 10 448 441 98 339 1608 655 1299 1274 484 533 214 286 222 1757 1527 145 1511 859 471 1945 1314 1270 411 1216 852 555 1085 1509 1354 26 1929 1721 1987 1159 1313 1523 1026 1018 1178 1197 173 1440 861 1492 545 1560 1847 747 43 1974 1593 873 1680 211 840 1862 150 1675 350 946 1129 1277 1383 63 1863 1599 838 1442 1508 1896 1821 6 1015 1460 1192 360 187 628 147 1836 191 107 1839 358 455 850 1265 738 1240 276 1331 606 799 1651 1938 1578 1403 1873 526 1759 1823 328 621 1813 401 563 1656 859 1070 1362 187 403 1315 1594 1978 1891 933 163 1575 1253 1211 1224 797 551 1470 1258 952 1532 1648 1534 1306 234 1346 810 1368 1290 796 716 1323 1307 281 1747 1120 1040 856 772 1976 1117 60 342 761 973 1981 1398 299 287 1877 916 1707 180 1300 1172 1851 435 1629 95 1008 54 1351 1695 1491 650 428 1974 1761 323 1773 1720 1211 117 476 1628 1431 124 544 47 749 1989 1237 1280 1866 1939 1961 549 640 1707 512 1205 1428 1400 1394 1181 591 1960 1368 475 894 636 2 1734 1890 1628 1619 772 1889 289 803 1313 355 1770 1996 1775 1989 376 1342 1073 297 1233 1692 654 116 1248 173 948 927 1699 603 1011 1847 1772 1463 1598 1838 1345 963 398 711 45 1958 542 397 1164 1196 1984 989 930 676 1142 343 1317 1328 474 513 783 1304 710 1668 141 679 1293 1837 562 957 1137 829 1093 571 1642 874 1998 1674 629 156 1229 804 850 1201 388 937 86 1625 536 60 1527 970 483 1556 531 1805 1653 1740 409 1631 863 1138 1245 1345 870 1915 1657 153 1414 622 791 927 1324 565 1784 1169 635 1343 816 847 1672 945 1223 879 222 1376 761 1818 955 40 103 557 1697 1960 1428 329 694 276 1497 500 564 1618 1762 1574 1178 1181 143 349 169 806 580 1977 855 1357 1769 1312 688 204 682 763 1184 1165 776 424 1370 1375 1046 1046 916 1445 1069 1372 1705 726 200 1426 501 126 1017 629 317 780 1586 1688 821 1138 221 1022 423 1641 1637 913 1475 1802 1130 782 1817 1765 1633 551 704 894 1266 751 1891 91 984 1185 1503 247 1957 1722 1879 867 715 1882 1088 31 739 1480 1141 117 1722 1387 996 1007 1807 1761 1230 1260 439 283 955 1759 681 575 612 400 1507 1637 1143 1993 1587 955 23 1609 1662 1793 10 261 1996 94 1177 930 58 505 1667 1533 87 1824 330 259 1575 645 1956 873 1699 507 1035 533 439 1438 126 2 419 184 1470 1185 1307 269 450 1171 135 768 1443 1343 1795 107 1824 914
输出 #3
32751264
提示
样例解释 1
由于调整操作产生的不愉快度太大,所以在本例中最好的方案是不进行调整;全部的 门课程中,最慢的在第 天出成绩; 同学 希望在第 天或之前出成绩,所以不会产生不愉快度; 同学 希望在第 天或之前出成绩,产生的不愉快度为 ; 同学 希望在第 天或之前出成绩,产生的不愉快度为 ; 同学 希望在第 天或之前出成绩,所以不会产生不愉快度; 不愉快度之和为 。
数据范围
| Case # | ||
|---|---|---|
| 1, 2 | , | |
| 3, 4 | , | |
| 5, 6, 7, 8 | , | |
| 9 - 12 | ||
| 13, 14 | , | |
| 15 - 20 |