QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#143451 | #5708. Hungry Fox | lmeowdn | 25 ✓ | 18ms | 5308kb | C++14 | 2.0kb | 2023-08-21 12:55:12 | 2023-08-21 12:55:14 |
Judging History
answer
#include<bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
template<typename T,typename U> T ceil(T x, U y) {return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U> T floor(T x, U y) {return (x>0?x/y:(x-y+1)/y);}
template<class T,class S> bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S> bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x) {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x) {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x) {return (x==0?-1:__builtin_ctzll(x));}
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
int read() {
int x=0,w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
return x*w;
}
const int N=1e5+5,inf=1e18;
int n,w,a[N],b[N],m,res,ans1,ans2;
signed main() {
n=read(), w=read();
rep(i,1,n) a[i]=read();
sort(a+1,a+n+1); a[0]=w;
int k=0; while(k<n&&a[k+1]<w) k++;
reverse(a+1,a+k+1);
rep(i,1,n) ans1+=min(abs(a[i]-a[i-1]),abs(a[i]-w));
sort(a+1,a+n+1);
int m=(n%2?n/2+1:n/2);
rep(i,1,m) b[i*2-1]=a[i];
reverse(a+m+1,a+n+1);
rep(i,m+1,n) b[(i-m)*2]=a[i];
b[0]=w;
res=0; rep(i,1,n) res+=max(abs(b[i]-b[i-1]),abs(b[i]-w)); chmax(ans2,res);
sort(a+1,a+n+1); reverse(a+1,a+n+1);
rep(i,1,m) b[i*2-1]=a[i];
reverse(a+m+1,a+n+1);
rep(i,m+1,n) b[(i-m)*2]=a[i];
b[0]=w;
res=0; rep(i,1,n) res+=max(abs(b[i]-b[i-1]),abs(b[i]-w)); chmax(ans2,res);
printf("%lld %lld\n",ans1,ans2);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 1
Accepted
time: 1ms
memory: 3652kb
input:
5 0 23 30 48 42 49
output:
49 195
result:
ok single line: '49 195'
Test #2:
score: 1
Accepted
time: 1ms
memory: 3704kb
input:
10 470 689 560 525 763 881 573 756 614 765 921
output:
451 3013
result:
ok single line: '451 3013'
Test #3:
score: 1
Accepted
time: 0ms
memory: 3760kb
input:
7 418 137 67 420 266 302 661 908
output:
841 3154
result:
ok single line: '841 3154'
Test #4:
score: 1
Accepted
time: 0ms
memory: 3652kb
input:
8 250 970 118 562 193 768 124 453 98
output:
872 4383
result:
ok single line: '872 4383'
Test #5:
score: 1
Accepted
time: 1ms
memory: 3660kb
input:
9 376 249 544 879 715 199 377 78 76 944
output:
868 4961
result:
ok single line: '868 4961'
Test #6:
score: 1
Accepted
time: 1ms
memory: 3640kb
input:
9 47 30 27 63 0 31 37 543 769 654
output:
769 3892
result:
ok single line: '769 3892'
Test #7:
score: 1
Accepted
time: 0ms
memory: 3656kb
input:
10 227 0 65 84 580 893 505 616 648 92 181
output:
893 5594
result:
ok single line: '893 5594'
Test #8:
score: 1
Accepted
time: 1ms
memory: 3644kb
input:
10 237 38 4 676 520 776 235 52 110 837 0
output:
837 5682
result:
ok single line: '837 5682'
Test #9:
score: 1
Accepted
time: 0ms
memory: 3708kb
input:
1000 530464 211908 420171 364765 85032 418733 21427 169977 281674 126677 158573 251977 313263 59134 219767 88251 109925 431245 458293 303377 37867 243022 21681 516033 53948 142169 438671 143138 110619 198589 451834 150762 328378 459258 14679 246562 493517 220083 99737 352977 362396 197889 283500 126...
output:
530014 360002009
result:
ok single line: '530014 360002009'
Test #10:
score: 1
Accepted
time: 13ms
memory: 5280kb
input:
100000 999553257 999866043 999644208 999872814 999627565 999972947 999973497 999626583 999774270 999896885 999801602 999820793 999663513 999958556 999719027 999737722 999564626 999723341 999634943 999853152 999788371 999588957 999637707 999911457 999886176 999814896 999675050 999647018 999564625 999...
output:
446741 29767886585
result:
ok single line: '446741 29767886585'
Test #11:
score: 1
Accepted
time: 1ms
memory: 3716kb
input:
700 581 346 837 134 904 336 68 431 21 40 525 92 384 564 455 821 262 428 997 547 351 840 324 163 454 498 397 28 748 929 784 503 876 353 493 704 981 959 697 126 286 989 51 155 818 666 671 703 165 247 160 80 672 764 99 341 140 473 821 850 315 962 13 541 153 369 55 926 579 838 713 499 775 137 97 608 372...
output:
998 364986
result:
ok single line: '998 364986'
Test #12:
score: 1
Accepted
time: 1ms
memory: 3716kb
input:
11 0 46 27 82 39 30 77 5 71 99 94 0
output:
99 798
result:
ok single line: '99 798'
Test #13:
score: 1
Accepted
time: 2ms
memory: 3772kb
input:
8000 811792 906262 991579 314340 884403 879420 173546 943479 890099 126842 173196 181614 101174 759831 859495 868712 985487 892070 895022 395373 775195 478938 899454 979417 984661 343334 989236 973024 183342 188534 62166 172192 905880 899218 640911 348649 864913 669929 93870 991924 991257 975145 889...
output:
999758 4050789688
result:
ok single line: '999758 4050789688'
Test #14:
score: 1
Accepted
time: 18ms
memory: 5056kb
input:
90000 407812686 863392876 798650883 921512574 797426637 665491360 828021815 305972444 388304016 960671165 801913529 852841306 261141801 245712991 515452920 730707836 174660157 995961192 775743797 68250612 475836341 80965537 955459183 93268713 994268760 805541602 742904216 447168641 152977740 2747929...
output:
999985909 45529864907418
result:
ok single line: '999985909 45529864907418'
Test #15:
score: 1
Accepted
time: 8ms
memory: 4884kb
input:
80001 532 621 129 244 464 700 323 570 449 796 800 621 133 444 749 370 763 412 45 886 846 188 414 656 783 11 626 492 146 179 648 962 15 879 858 440 823 626 81 444 369 722 196 71 249 898 39 833 492 843 717 971 16 812 285 356 391 593 515 528 973 13 541 178 23 566 47 19 57 426 659 163 168 991 326 43 936...
output:
1000 40095053
result:
ok single line: '1000 40095053'
Test #16:
score: 1
Accepted
time: 9ms
memory: 4960kb
input:
80002 783088 16695 769607 303926 806467 598181 123638 134452 986034 835774 951431 673323 573170 106111 581991 914863 886606 425375 225178 821061 774797 183456 947700 334491 13244 637702 324065 993026 79749 258731 876185 380210 241494 220287 142758 839177 103965 776420 895333 513408 976432 735149 881...
output:
999996 39994480900
result:
ok single line: '999996 39994480900'
Test #17:
score: 1
Accepted
time: 16ms
memory: 4844kb
input:
80002 666625980 207421631 992982976 227623091 290604473 275318222 364308215 60495698 563276042 602640275 669019801 441938891 758117615 684933247 673332228 507755764 935047154 739295303 735132710 918777899 575347360 725627659 347189963 732528614 870254630 314952787 139513713 514608378 700824679 79023...
output:
999992124 39832698437015
result:
ok single line: '999992124 39832698437015'
Test #18:
score: 1
Accepted
time: 17ms
memory: 5280kb
input:
100000 97512199 81242089 98303144 33326736 640060762 664278674 20050409 896408834 937887965 406628311 1921763 74337319 15175167 752856076 19713771 332502691 155817694 131709365 32771073 72613532 204696573 780905700 669532052 51130601 675096173 74818678 59409523 321787377 790709397 269367176 38814567...
output:
999981473 49781845377535
result:
ok single line: '999981473 49781845377535'
Test #19:
score: 1
Accepted
time: 1ms
memory: 3712kb
input:
100 0 129 131 872 789 758 359 83 65 1 153 431 284 905 794 452 16 644 974 757 78 695 257 65 130 187 849 70 584 711 140 628 506 844 366 864 792 71 621 901 812 48 829 175 130 542 109 373 320 787 891 457 430 751 428 723 892 903 635 708 711 439 313 440 968 682 170 141 735 199 844 968 251 98 484 702 759 1...
output:
974 66854
result:
ok single line: '974 66854'
Test #20:
score: 1
Accepted
time: 1ms
memory: 3768kb
input:
1000 0 447 664 940 798 852 25 654 221 853 879 857 193 446 218 128 789 479 169 570 948 379 740 444 156 512 705 285 628 296 148 769 389 350 123 608 720 983 907 862 944 715 236 10 814 226 250 802 818 293 975 555 461 856 584 603 162 268 986 567 812 244 977 594 186 650 642 846 709 219 977 505 316 173 985...
output:
1000 661554
result:
ok single line: '1000 661554'
Test #21:
score: 1
Accepted
time: 1ms
memory: 3656kb
input:
1000 0 727385 66257 117923 505828 964960 744701 40178 533137 862096 513452 980053 968650 670234 54331 349777 945392 658902 992735 721045 657427 781123 211846 71828 297242 206495 886214 73781 658313 305366 681577 388337 705368 739963 766065 680059 903460 899621 121373 373557 513717 38631 572489 38188...
output:
999964 691187640
result:
ok single line: '999964 691187640'
Test #22:
score: 1
Accepted
time: 14ms
memory: 5216kb
input:
100000 0 7693 6743 2940 2807 7496 8556 5459 8408 109 3365 7289 1038 8657 671 6469 1572 9941 7784 1270 6784 1931 411 209 5017 2974 8311 3866 5526 524 4234 9180 8230 1772 6182 1125 739 5181 9647 6165 1049 6878 2658 1244 3583 9476 3538 5887 7780 3675 8162 2459 2645 4586 2941 4591 5373 2534 3214 4464 49...
output:
10000 666952810
result:
ok single line: '10000 666952810'
Test #23:
score: 1
Accepted
time: 11ms
memory: 5308kb
input:
100000 0 302260367 380708949 771057230 657756795 545909011 10898292 452151872 544887273 800868234 365323901 332427351 598809894 394148999 443570112 942838952 887365690 460703269 4648107 533685252 452131335 381667107 283044073 926347799 908333672 818844871 714234793 849817594 579875719 77892473 29237...
output:
999988350 66682342806027
result:
ok single line: '999988350 66682342806027'
Test #24:
score: 1
Accepted
time: 17ms
memory: 5200kb
input:
100000 0 214145951 781041459 471560579 531901852 367686129 947649966 890621708 83623239 134391533 500770892 986014170 611444143 626340906 180188659 838359401 181435930 222417068 973939357 998089798 688335565 754702718 389827543 575419262 218248564 609744860 265964825 25475424 3318774 35903640 295209...
output:
999985959 66640445374134
result:
ok single line: '999985959 66640445374134'
Test #25:
score: 1
Accepted
time: 1ms
memory: 3660kb
input:
10 8 4 0 6 2 2 2 1 2 4 1
output:
8 60
result:
ok single line: '8 60'