QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #325120 | #5606. A Musical Question | weilaifuture# | AC ✓ | 130ms | 7584kb | C++14 | 824b | 2024-02-11 04:23:31 | 2024-02-11 04:23:32 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
int c,n,ans, a[N], tmp1, tmp2;
bool dp[N][N][N];
int main(){
cin>>c>>n;
for(int i=1;i<=n;i++) cin>>a[i];
dp[0][0][0]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<=c;j++) for(int k=0;k<=c;k++) dp[i%2][j][k]=0;
for(int j=0;j<=c;j++){
for(int k=0;k<=c;k++){
dp[i&1][j][k] = dp[1-i%2][j][k];
if(j>=a[i]) dp[i&1][j][k] |= dp[1-i%2][j-a[i]][k];
if(k>=a[i]) dp[i&1][j][k] |= dp[1-i%2][j][k-a[i]];
}
}
}
for(int j=0;j<=c;j++) for(int k=0;k<=c;k++) if(dp[n%2][j][k]){if(ans<j+k) ans=j+k,tmp1=j,tmp2=k; else if(ans == j+k && abs(j-k) < abs(tmp1-tmp2)){tmp1=j, tmp2=k;}}
cout<<max(tmp1,tmp2)<<" "<<min(tmp1,tmp2);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5732kb
input:
100 5 10 20 40 60 85
output:
100 95
result:
ok single line: '100 95'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
100 5 10 20 30 40 50
output:
80 70
result:
ok single line: '80 70'
Test #3:
score: 0
Accepted
time: 130ms
memory: 7584kb
input:
1000 1000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
output:
500 500
result:
ok single line: '500 500'
Test #4:
score: 0
Accepted
time: 110ms
memory: 6724kb
input:
1000 1000 894 723 513 814 708 790 838 766 572 681 564 601 588 606 519 719 538 809 569 642 756 747 773 888 692 645 887 820 504 861 684 756 585 576 679 511 689 607 585 875 897 507 630 708 718 810 860 896 579 875 810 615 742 783 525 757 651 659 591 835 517 608 606 634 524 828 700 662 782 581 593 789 62...
output:
899 898
result:
ok single line: '899 898'
Test #5:
score: 0
Accepted
time: 94ms
memory: 6368kb
input:
999 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1...
output:
0 0
result:
ok single line: '0 0'
Test #6:
score: 0
Accepted
time: 1ms
memory: 5680kb
input:
100 4 40 50 20 60
output:
90 80
result:
ok single line: '90 80'
Test #7:
score: 0
Accepted
time: 1ms
memory: 5632kb
input:
50 50 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000
output:
0 0
result:
ok single line: '0 0'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
100 8 52 9 2 70 61 14 8 59
output:
83 81
result:
ok single line: '83 81'
Test #9:
score: 0
Accepted
time: 2ms
memory: 4664kb
input:
500 50 255 256 262 263 271 281 291 293 293 296 296 299 305 306 306 311 316 317 317 321 332 340 344 346 346 346 357 361 367 383 391 397 406 413 417 419 431 443 444 449 449 452 457 457 468 469 470 484 492 495
output:
495 492
result:
ok single line: '495 492'
Test #10:
score: 0
Accepted
time: 0ms
memory: 5684kb
input:
20 20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
output:
10 10
result:
ok single line: '10 10'
Test #11:
score: 0
Accepted
time: 110ms
memory: 6776kb
input:
1000 1000 673 822 553 843 797 563 888 786 751 877 518 600 698 736 895 521 534 767 622 613 773 833 629 810 677 731 570 547 787 648 675 765 885 880 659 884 885 570 510 777 889 657 600 630 706 614 636 530 648 667 785 849 886 558 523 695 832 628 864 858 689 586 891 758 868 578 890 706 503 507 845 787 62...
output:
899 899
result:
ok single line: '899 899'
Test #12:
score: 0
Accepted
time: 110ms
memory: 5948kb
input:
1000 1000 807 757 556 591 611 690 763 542 559 839 708 771 553 869 642 585 658 580 816 769 544 713 732 708 857 747 587 855 885 532 892 703 667 622 734 610 871 807 624 881 569 872 584 755 543 502 513 837 538 530 630 699 787 833 730 739 538 547 657 723 558 673 735 796 790 724 825 646 865 754 859 871 75...
output:
899 899
result:
ok single line: '899 899'
Test #13:
score: 0
Accepted
time: 9ms
memory: 6876kb
input:
1000 50 34 40 28 47 44 27 28 30 31 27 45 47 31 49 30 47 44 43 30 43 26 37 43 40 48 44 43 45 47 40 31 32 25 42 43 27 37 45 26 39 28 30 42 35 44 29 44 36 49 34
output:
938 938
result:
ok single line: '938 938'
Test #14:
score: 0
Accepted
time: 7ms
memory: 6284kb
input:
1000 50 941 739 509 571 619 653 911 977 797 467 569 937 659 577 947 853 599 701 691 983 941 809 907 569 557 773 929 769 751 503 523 773 523 593 797 661 673 821 881 719 967 673 907 977 757 643 997 661 613 617
output:
997 990
result:
ok single line: '997 990'
Test #15:
score: 0
Accepted
time: 3ms
memory: 5660kb
input:
1000 50 863 863 599 887 599 719 691 709 487 631 557 503 883 967 593 853 521 641 521 677 827 739 593 683 593 941 811 853 877 853 673 587 863 659 971 557 577 661 461 743 743 509 503 503 479 499 971 887 617 919
output:
1000 996
result:
ok single line: '1000 996'
Test #16:
score: 0
Accepted
time: 3ms
memory: 6260kb
input:
500 50 269 263 257 251 257 263 251 257 27 257 263 27 269 263 263 269 263 269 27 27 263 27 257 257 263 263 251 269 257 251 27 27 27 257 251 251 263 27 269 257 251 269 251 27 27 263 251 269 263 269
output:
431 404
result:
ok single line: '431 404'
Test #17:
score: 0
Accepted
time: 1ms
memory: 5672kb
input:
90 50 15 255 31 511 511 15 127 127 255 255 511 31 15 31 127 15 127 511 127 127 31 511 63 15 15 31 63 511 511 63 511 511 511 63 15 255 511 15 255 63 31 511 255 255 31 127 127 511 15 255
output:
90 78
result:
ok single line: '90 78'
Test #18:
score: 0
Accepted
time: 3ms
memory: 6876kb
input:
654 25 511 63 31 255 511 255 63 255 15 31 15 63 255 31 127 255 15 511 31 63 255 255 127 127 127
output:
653 653
result:
ok single line: '653 653'
Test #19:
score: 0
Accepted
time: 8ms
memory: 6176kb
input:
511 250 459 441 441 467 275 377 324 314 419 449 227 219 209 230 314 208 459 208 413 265 467 324 458 298 329 475 275 439 209 458 307 458 227 324 419 275 377 434 449 298 377 329 321 459 324 275 344 230 459 265 434 324 237 324 475 458 439 413 219 329 275 449 307 467 324 203 203 265 298 324 275 329 321 ...
output:
510 510
result:
ok single line: '510 510'