QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#613536#8524. Weather ForecastTecy#WA 1ms4020kbC++201.4kb2024-10-05 14:10:392024-10-05 14:13:26

Judging History

你现在查看的是最新测评结果

  • [2024-10-05 14:13:26]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4020kb
  • [2024-10-05 14:10:39]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
const double eps = 1e-6;
void solve() {
    int n,k;
    cin >> n >> k;
    vector<int>a(n + 1);
    for(int i = 1;i <= n;i++) cin >> a[i];
    auto check = [&](double x){
        vector<double>b(n + 1),suf(n + 2);
        for(int i = 1;i <= n;i++){
            b[i] = (double)(a[i] - x);
            // cerr << b[i] << ' ';
        }
        // cerr << endl;
        suf[n + 1] = 0;
        for(int i = n;i;i--){
            suf[i] = suf[i + 1] + b[i];
        }
        if(suf[1]<=eps)return false;
        int res = 1;
        double sum = 0;
        for(int i = 1;i < n;i++){
            sum += b[i];
            // cerr << sum << ' ' << suf[i + 1] << endl;
            if(b[i + 1] <= eps && sum + b[i + 1] >= -eps) continue; 
            if(sum >= eps && suf[i + 1] >= eps){
                res++;
                sum = 0;
            }
        }
        return res >= k;
    };    
    double l = 0,r = 1e3;
    while(r - l > eps){
        double mid = (l + r) / 2;
        // cerr << mid << ' ' << l << ' ' << r << endl;
        if(check(mid)) l = mid;
        else r = mid;
    }
    cout << fixed << setprecision(12) << l << '\n';
}
signed main() {
    ios::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);

    int T = 1;
    // cin >> T;
    for (int i = 1; i <= T; i++) {
        solve();
    }

    return 0;
}
/*
7 3
1 3 1 2 2 2 1
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3940kb

input:

7 3
1 3 1 2 2 2 1

output:

1.666666008532

result:

ok found '1.66667', expected '1.66667', error '0.00000'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3776kb

input:

1 1
1

output:

0.999998301268

result:

ok found '1.00000', expected '1.00000', error '0.00000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3720kb

input:

2 1
2 1

output:

1.499999314547

result:

ok found '1.50000', expected '1.50000', error '0.00000'

Test #4:

score: 0
Accepted
time: 1ms
memory: 3772kb

input:

3 2
2 4 4

output:

2.999998629093

result:

ok found '3.00000', expected '3.00000', error '0.00000'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3948kb

input:

4 2
6 7 3 12

output:

6.499999202788

result:

ok found '6.50000', expected '6.50000', error '0.00000'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3720kb

input:

5 3
17 23 13 12 21

output:

16.499998979270

result:

ok found '16.50000', expected '16.50000', error '0.00000'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3872kb

input:

7 4
3 37 46 23 46 6 31

output:

22.999998182058

result:

ok found '23.00000', expected '23.00000', error '0.00000'

Test #8:

score: 0
Accepted
time: 0ms
memory: 4020kb

input:

10 5
30 91 36 53 74 91 37 1 76 3

output:

39.499999023974

result:

ok found '39.50000', expected '39.50000', error '0.00000'

Test #9:

score: -100
Wrong Answer
time: 0ms
memory: 3780kb

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:

462.000000290573

result:

wrong answer 1st numbers differ - expected: '483.00000', found: '462.00000', error = '21.00000'