QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#442288#8524. Weather Forecastucup-team3548#WA 0ms4048kbC++201.5kb2024-06-15 10:53:422024-06-15 10:53:42

Judging History

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

  • [2024-06-15 10:53:42]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:4048kb
  • [2024-06-15 10:53:42]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = double;

constexpr int N = 3e5 + 5;
const ll inf = 1e16;

void solve(){
    int n, k;
    cin >> n >> k;
    vector<int> a(n), pre(n + 1);
    for(int i = 0; i < n; ++i){
        cin >> a[i];
        pre[i + 1] = pre[i] + a[i];
    }

    vector<int> dp(n + 1);
    auto check = [&](double x){
        fill(dp.begin(), dp.end(), 0);
        vector<int> len;
        len.push_back(0);
        for(int i = 1; i <= n; ++i){
            if(pre[len.back()] - x * len.back() <= pre[i] - x * i){
                len.push_back(i);
                dp[i] = len.size();
                continue;
            }
            int p = upper_bound(len.begin(), len.end(), i, [&](const int &u, const int &v){
                return pre[u] - x * u < pre[v] - x * v;
            }) - len.begin();
            if(p == 0)continue;
            dp[i] = p;
            len[p] = i;
        }
        // for(int i = 1; i <= n; ++i){
        //     cout << dp[i] << ' ';
        // }
        // cout << x << '\n';
        return dp.back() >= k;
    };

    double l = 1, r = 1001;
    while(r - l > 1e-5){
        double mid = (l + r) / 2;
        if(check(mid)){
            l = mid;
        }else{
            r = mid;
        }
    }
    cout << l << '\n';
}


int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.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: 3856kb

input:

7 3
1 3 1 2 2 2 1

output:

1.66666

result:

ok found '1.66666', expected '1.66667', error '0.00001'

Test #2:

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

input:

1 1
1

output:

1

result:

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

Test #3:

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

input:

2 1
2 1

output:

1.49999

result:

ok found '1.49999', expected '1.50000', error '0.00001'

Test #4:

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

input:

3 2
2 4 4

output:

3.33333

result:

wrong answer 1st numbers differ - expected: '3.00000', found: '3.33333', error = '0.33333'