QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#515178#8524. Weather Forecastk1nsom#TL 199ms7940kbC++171.2kb2024-08-11 15:46:032024-08-11 15:46:04

Judging History

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

  • [2024-08-11 15:46:04]
  • 评测
  • 测评结果:TL
  • 用时:199ms
  • 内存:7940kb
  • [2024-08-11 15:46:03]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define int long long
#define PII pair<int, int>
const int mod = 1e9 + 7;
const int N = 2e5 + 5;
int n, k, a[N], pre[N], dp[N];
double tmp[N]; // dp[i]表示i节点出去到n的方案数
bool check(double x)
{
    fill(dp + 1, dp + 1 + n, -1e9);
    for (int i = 1; i <= n; i++)
        tmp[i] = a[i] - x, tmp[i] += tmp[i - 1];
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < i; j++)
        {
            if (tmp[i] - tmp[j] >= 0)
                dp[i] = max(dp[i], dp[j] + 1);
        }
    }
    return dp[n] >= k;
}
void solve()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i], pre[i] = a[i] + pre[i - 1];
    double l = 0, r = pre[n] * 1.0 / n, ans = 0;
    for (int i = 1; i <= 200; i++)
    {
        double mid = (l + r) * 0.5;
        if (check(mid))
        {
            ans = mid;
            l = mid;
        }
        else
            r = mid;
    }
    cout << fixed << setprecision(10) << ans;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    // cin >> T;
    while (T--)
        solve();

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 7908kb

input:

7 3
1 3 1 2 2 2 1

output:

1.6666666667

result:

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

Test #2:

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

input:

1 1
1

output:

1.0000000000

result:

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

Test #3:

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

input:

2 1
2 1

output:

1.5000000000

result:

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

Test #4:

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

input:

3 2
2 4 4

output:

3.0000000000

result:

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

Test #5:

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

input:

4 2
6 7 3 12

output:

6.5000000000

result:

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

Test #6:

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

input:

5 3
17 23 13 12 21

output:

16.5000000000

result:

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

Test #7:

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

input:

7 4
3 37 46 23 46 6 31

output:

23.0000000000

result:

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

Test #8:

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

input:

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

output:

39.5000000000

result:

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

Test #9:

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

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:

483.0000000000

result:

ok found '483.00000', expected '483.00000', error '0.00000'

Test #10:

score: 0
Accepted
time: 199ms
memory: 5956kb

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:

395.0000000000

result:

ok found '395.00000', expected '395.00000', error '0.00000'

Test #11:

score: -100
Time Limit Exceeded

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:


result: