QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#442288 | #8524. Weather Forecast | ucup-team3548# | WA | 0ms | 4048kb | C++20 | 1.5kb | 2024-06-15 10:53:42 | 2024-06-15 10:53:42 |
Judging History
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'