QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #477633 | #9129. Quotient Sum | ucup-team1231# | WA | 4ms | 5876kb | C++14 | 646b | 2024-07-14 07:48:40 | 2024-07-14 07:48:40 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long int LLI;
LLI A[200000];
LLI dp[200000];
int main() {
int i;
int N;
scanf("%d",&N);
for (i = 0; i < N; i++) scanf("%lld",&A[i]);
sort(A,A+N);
LLI ans = 0;
for (i = 1; i < N; i++) {
dp[i] = dp[i-1]+A[i]/A[i-1];
LLI k = A[i]/A[i-1];
for (LLI d = k; d <= k+5; d++) {
if (d == 1) continue;
LLI b = (A[i]-1+d-2)/(d-1);
int p = lower_bound(A,A+N,b)-A;
if (p < i) dp[i] = min(dp[i],dp[p]+A[i]/A[p]);
}
}
cout << dp[N-1] << endl;
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5736kb
input:
3 2 3 6
output:
3
result:
ok "3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
2 15 4
output:
3
result:
ok "3"
Test #3:
score: 0
Accepted
time: 1ms
memory: 5656kb
input:
9 284791808 107902 13660981249408 4622332661 13405199 24590921 361 244448137 16077087227955422
output:
4580
result:
ok "4580"
Test #4:
score: 0
Accepted
time: 1ms
memory: 5760kb
input:
9 12 9 5 17 2 6 7 1 15
output:
6
result:
ok "6"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3720kb
input:
10 19 13 18 11 20 16 6 8 17 3
output:
4
result:
ok "4"
Test #6:
score: 0
Accepted
time: 0ms
memory: 5684kb
input:
8 5 7 11 16 2 15 1 20
output:
7
result:
ok "7"
Test #7:
score: 0
Accepted
time: 0ms
memory: 5724kb
input:
10 13 2 19 11 15 9 16 5 12 1
output:
7
result:
ok "7"
Test #8:
score: 0
Accepted
time: 1ms
memory: 5812kb
input:
8 9 1 14 11 3 12 8 20
output:
7
result:
ok "7"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
4 4 6 20 3
output:
5
result:
ok "5"
Test #10:
score: 0
Accepted
time: 1ms
memory: 5804kb
input:
382 1495 1297 1197 976 1335 486 1850 992 1483 1269 1898 1593 237 1342 711 957 1992 1401 1413 206 917 1831 1444 698 1291 1987 231 1559 1119 1822 1790 471 736 496 1157 1886 1974 699 1702 321 325 758 683 1826 1051 95 632 456 1224 1590 1394 1854 1226 1963 1926 1819 989 34 980 371 535 807 1541 144 433 12...
output:
11
result:
ok "11"
Test #11:
score: 0
Accepted
time: 0ms
memory: 5804kb
input:
317 1565 1374 387 1215 766 1670 862 673 1391 70 727 152 182 26 1111 1430 64 1318 349 994 780 1762 1993 552 715 1943 967 972 1039 646 617 1822 373 486 1863 1179 1840 1781 1963 220 773 671 126 613 719 1660 334 1851 65 707 1862 490 1466 1590 1717 1723 656 1526 1138 31 1976 1823 1335 1719 397 612 593 13...
output:
8
result:
ok "8"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3756kb
input:
100 1070 947 7 1735 476 1172 995 2000 536 15 1499 656 1810 1435 639 1647 61 630 4 754 1594 442 1644 1743 5 629 1879 1707 1174 1984 1526 1829 1449 783 1483 1734 1032 494 537 1872 1117 1316 1069 780 520 689 31 1970 1653 1071 251 360 1063 988 1154 638 547 525 264 495 273 436 967 633 462 1863 164 402 18...
output:
12
result:
ok "12"
Test #13:
score: 0
Accepted
time: 1ms
memory: 3832kb
input:
495 368 27 1415 966 351 1575 449 1982 15 1207 1806 1483 1304 1488 750 1751 1047 314 1833 1365 1281 589 1062 419 1430 345 41 230 1248 11 338 1139 1146 1892 281 1994 950 26 1247 817 1250 131 1954 631 1020 1705 382 220 172 1434 1841 1866 849 793 1236 53 1275 1366 1038 1889 615 1652 218 1862 84 377 76 1...
output:
19
result:
ok "19"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
452 1711 258 865 1330 1923 4 1656 652 1660 1768 603 1841 646 1810 1235 200 503 1083 418 511 1803 886 54 213 1914 734 1531 1941 272 1686 1873 1831 1367 1746 141 404 1538 989 768 1830 1684 426 527 1872 1105 1655 540 1444 331 767 1896 49 1141 921 772 307 614 764 848 1997 1406 339 63 828 416 1891 1925 6...
output:
11
result:
ok "11"
Test #15:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
61 320 456 426 201 1105 1894 570 661 1307 618 956 1185 1241 6 574 1236 604 462 1900 1488 697 1688 1085 775 635 747 1252 1721 431 192 768 1798 1712 686 1496 932 1309 1431 904 1467 1863 804 856 1682 1159 78 1276 211 942 848 270 225 117 302 1418 1951 534 1345 591 110 1967
output:
19
result:
ok "19"
Test #16:
score: 0
Accepted
time: 2ms
memory: 5852kb
input:
6007 926195740081456592 954460021832145143 601395744686943902 21575530228356921 463431657670752021 711276919720293649 916086948281828983 942717046975828490 627872019769751663 375556646744053894 531095909932455304 993855300776486066 208335586285140634 319193845177757965 985795314563730251 10507706789...
output:
12
result:
ok "12"
Test #17:
score: -100
Wrong Answer
time: 4ms
memory: 5876kb
input:
8261 284791808 107902 13660981249408 4622332661 13405199 24590921 361 244448137 16077087227955422 29020 2999 243823 11405 3084850839644 51410 1293 598217528 6419212814 19670 42431 16305842936592 588083868939790 35416223344083524 1670928183457 462015428 19431 7573789315 819 4594126473685 8554104 1422...
output:
65
result:
wrong answer 1st words differ - expected: '63', found: '65'