QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#466714 | #8524. Weather Forecast | ivaziva | TL | 2877ms | 28512kb | C++17 | 2.3kb | 2024-07-08 04:15:23 | 2024-07-08 04:15:24 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define MAXN 200010
long long n,k;
long long a[MAXN];
double b[MAXN],pref[MAXN];
map<double,long long> mapa;
long long seg[MAXN*4];
vector<long long> vec;
void update(long long node,long long l,long long r,long long pos,long long val)
{
if (l==r) seg[node]=val;
else
{
long long mid=(l+r)/2;
if (pos<=mid) update(2*node,l,mid,pos,val);
else update(2*node+1,mid+1,r,pos,val);
seg[node]=max(seg[2*node],seg[2*node+1]);
}
}
long long query(long long node,long long l,long long r,long long a,long long b)
{
if (a>b) return 0;
if (l==a and r==b) return seg[node];
long long mid=(l+r)/2;
return max(query(2*node,l,mid,a,min(b,mid)),query(2*node+1,mid+1,r,max(a,mid+1),b));
}
bool check(double t)
{
//cout<<t<<endl;
for (long long i=1;i<=n;i++) b[i]=(double)(a[i])-t;
/*for (long long i=1;i<=n;i++) cout<<b[i]<<" ";
cout<<endl;*/
pref[0]=0;
for (long long i=1;i<=n;i++) pref[i]=pref[i-1]+b[i];
/*for (long long i=1;i<=n;i++) cout<<pref[i]<<" ";
cout<<endl;*/
for (long long i=1;i<=n;i++) mapa[pref[i]]=1;
long long pret=1;
for (auto&p:mapa) {p.second=pret;pret++;}
vec.push_back(0);
for (long long i=1;i<=n;i++)
{
if (pref[i]<0) continue;
vec.push_back(mapa[pref[i]]);
}
long long siz=vec.size()-1;
/*for (long long i=1;i<=siz;i++) cout<<vec[i]<<" ";
cout<<endl;*/
mapa.clear();
for (long long i=1;i<=4*n;i++) seg[i]=0;
long long br;
for (long long i=1;i<=siz;i++)
{
long long lis=query(1,1,n,1,vec[i])+1;
update(1,1,n,vec[i],lis);
if (i==siz) br=lis;
}
vec.clear();
if (br>=k) return true;
else return false;
}
int main()
{
ios_base::sync_with_stdio(false);
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>k;
for (long long i=1;i<=n;i++) cin>>a[i];
long long sum=0;
for (long long i=1;i<=n;i++) sum+=a[i];
double sredina=sum*1.00/n;
double l=0,r=sredina;
double rez=0;
while (r-l>=0.00001)
{
double mid=(l+r)/2;
if (check(mid)) {rez=mid;l=mid;}
else r=mid;
}
cout<<fixed<<showpoint<<setprecision(5)<<rez<<endl;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 8012kb
input:
7 3 1 3 1 2 2 2 1
output:
1.66667
result:
ok found '1.66667', expected '1.66667', error '0.00000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 8016kb
input:
1 1 1
output:
0.99999
result:
ok found '0.99999', expected '1.00000', error '0.00001'
Test #3:
score: 0
Accepted
time: 1ms
memory: 9864kb
input:
2 1 2 1
output:
1.49999
result:
ok found '1.49999', expected '1.50000', error '0.00001'
Test #4:
score: 0
Accepted
time: 0ms
memory: 7976kb
input:
3 2 2 4 4
output:
3.00000
result:
ok found '3.00000', expected '3.00000', error '0.00000'
Test #5:
score: 0
Accepted
time: 1ms
memory: 7956kb
input:
4 2 6 7 3 12
output:
6.50000
result:
ok found '6.50000', expected '6.50000', error '0.00000'
Test #6:
score: 0
Accepted
time: 1ms
memory: 7944kb
input:
5 3 17 23 13 12 21
output:
16.49999
result:
ok found '16.49999', expected '16.50000', error '0.00001'
Test #7:
score: 0
Accepted
time: 1ms
memory: 7816kb
input:
7 4 3 37 46 23 46 6 31
output:
23.00000
result:
ok found '23.00000', expected '23.00000', error '0.00000'
Test #8:
score: 0
Accepted
time: 1ms
memory: 9928kb
input:
10 5 30 91 36 53 74 91 37 1 76 3
output:
39.50000
result:
ok found '39.50000', expected '39.50000', error '0.00000'
Test #9:
score: 0
Accepted
time: 0ms
memory: 7976kb
input:
100 50 593 336 577 842 505 78 665 825 990 895 952 782 721 242 421 951 786 994 238 154 356 483 686 143 220 473 920 353 738 690 96 915 913 157 412 882 465 585 963 635 68 72 901 143 50 558 310 504 987 97 588 987 841 829 780 497 758 909 503 585 91 657 912 870 663 606 748 492 175 92 375 768 773 206 676 8...
output:
482.99999
result:
ok found '482.99999', expected '483.00000', error '0.00001'
Test #10:
score: 0
Accepted
time: 8ms
memory: 10164kb
input:
1000 500 74 796 330 98 801 45 160 90 432 788 873 109 714 307 407 94 360 136 198 912 744 902 549 398 478 590 663 983 956 267 201 332 610 249 698 268 700 755 902 485 327 539 203 397 721 971 951 378 674 159 269 182 473 993 84 832 808 908 73 608 842 411 465 886 348 153 924 871 729 1 279 949 475 71 982 3...
output:
394.99999
result:
ok found '394.99999', expected '395.00000', error '0.00001'
Test #11:
score: 0
Accepted
time: 78ms
memory: 13184kb
input:
10000 5000 821 298 787 377 804 127 552 321 868 2 375 982 196 201 154 323 49 881 81 182 265 584 179 530 130 213 469 887 667 771 637 634 872 528 560 552 168 299 603 668 244 275 838 524 874 508 751 52 83 224 957 910 349 102 285 236 897 44 797 332 834 978 534 730 260 178 842 877 961 219 378 552 294 796 ...
output:
390.49999
result:
ok found '390.49999', expected '390.50000', error '0.00001'
Test #12:
score: 0
Accepted
time: 2194ms
memory: 28236kb
input:
200000 100000 240 455 802 920 682 343 84 855 428 864 623 114 400 668 175 66 376 309 970 367 526 980 47 962 793 90 494 352 721 69 920 233 442 103 812 38 644 987 718 897 756 752 490 436 476 46 690 434 869 179 519 74 833 349 970 328 2 77 964 782 383 536 461 736 540 906 249 296 8 35 259 865 267 831 604 ...
output:
391.33333
result:
ok found '391.33333', expected '391.33333', error '0.00000'
Test #13:
score: 0
Accepted
time: 1589ms
memory: 28316kb
input:
199998 23727 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:
0.99999
result:
ok found '0.99999', expected '1.00000', error '0.00001'
Test #14:
score: 0
Accepted
time: 1923ms
memory: 28408kb
input:
199997 155 1 2 1 2 2 2 1 1 2 2 1 1 2 2 2 1 1 1 2 2 2 1 1 1 2 2 2 2 1 1 2 1 1 2 2 1 1 1 1 1 2 1 2 2 2 1 2 2 2 2 2 2 2 2 2 1 1 1 2 1 1 2 1 2 1 2 1 2 2 1 1 2 1 1 1 2 1 2 2 2 1 1 2 2 1 1 1 1 2 2 1 2 1 1 2 2 2 2 1 2 2 1 1 1 1 1 2 2 1 1 2 2 1 1 1 2 2 1 1 1 2 1 2 1 1 2 2 2 1 2 2 2 1 1 2 1 2 2 1 2 2 1 2 1 1...
output:
1.50029
result:
ok found '1.50029', expected '1.50029', error '0.00000'
Test #15:
score: 0
Accepted
time: 2688ms
memory: 28364kb
input:
199997 5668 4 1 1 4 4 5 3 5 4 2 3 2 4 3 3 4 2 2 2 3 4 1 1 5 1 4 5 3 3 2 2 2 5 4 1 1 5 5 3 1 4 2 2 5 4 4 5 1 4 1 4 1 4 1 4 2 1 4 4 2 1 3 5 4 4 4 1 2 1 4 5 2 5 1 1 1 5 4 5 2 5 5 5 1 2 5 1 2 3 3 2 2 1 5 1 5 1 3 5 4 3 1 2 2 4 3 2 1 4 3 3 3 2 4 2 3 1 5 5 5 4 4 3 3 3 4 2 3 5 2 3 4 5 5 1 1 4 1 2 2 4 5 2 4 ...
output:
2.99534
result:
ok found '2.99534', expected '2.99534', error '0.00000'
Test #16:
score: 0
Accepted
time: 2067ms
memory: 28512kb
input:
199999 40 7 8 8 2 10 1 2 10 1 4 3 7 2 2 5 7 3 7 9 2 9 1 9 9 7 9 4 5 5 6 10 4 8 1 8 2 7 1 8 4 4 10 4 7 3 2 7 8 10 9 6 9 4 5 7 7 2 9 4 7 1 7 3 6 3 1 7 10 6 1 4 7 1 4 2 3 5 1 5 10 5 5 10 5 10 4 7 3 2 4 3 8 8 6 1 5 1 3 8 5 1 9 5 1 4 2 5 2 8 4 3 6 5 5 10 7 6 6 4 9 6 10 3 4 8 7 2 6 9 7 6 9 2 8 9 7 5 8 4 8...
output:
5.50152
result:
ok found '5.50152', expected '5.50152', error '0.00000'
Test #17:
score: 0
Accepted
time: 2877ms
memory: 28216kb
input:
199998 5 99 76 31 60 81 98 31 57 91 45 28 40 66 41 69 53 67 13 28 96 48 52 67 26 50 33 51 72 71 35 67 79 41 33 74 43 58 43 38 24 3 71 16 16 66 62 15 24 95 99 53 59 13 96 18 38 75 96 84 99 43 40 72 46 8 34 66 68 96 79 14 10 41 60 61 26 48 14 34 16 40 68 71 24 5 30 89 26 25 80 18 48 58 35 59 76 59 76 ...
output:
50.49864
result:
ok found '50.49864', expected '50.49864', error '0.00000'
Test #18:
score: 0
Accepted
time: 2758ms
memory: 28380kb
input:
200000 3 772 660 48 48 244 440 394 172 177 335 139 778 502 336 571 880 552 539 797 111 428 654 720 549 679 510 503 426 290 358 2 358 649 811 327 237 829 767 867 111 122 223 725 141 310 69 682 694 529 315 743 23 335 485 272 426 321 449 370 202 779 345 165 826 117 371 785 115 709 333 816 379 682 479 9...
output:
500.84251
result:
ok found '500.84251', expected '500.84252', error '0.00001'
Test #19:
score: -100
Time Limit Exceeded
input:
200000 1 699 581 24 253 228 784 562 694 404 878 909 661 750 889 344 167 931 267 4 792 73 639 749 368 197 813 644 920 738 793 38 70 609 82 182 120 433 814 270 582 298 189 867 451 816 777 20 253 603 868 790 909 995 161 701 195 735 63 365 316 313 526 632 103 808 883 9 374 722 493 64 476 324 456 617 325...