QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#442393 | #8524. Weather Forecast | ucup-team3282# | TL | 0ms | 0kb | C++14 | 864b | 2024-06-15 11:36:09 | 2024-06-15 11:36:09 |
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+9;
int n, k;
double a[N];
bool check(double mid) {
int nw=1,cnt=0;
while(cnt<k-1){
double sum=0,num=0;
bool flag=false;
for(;nw<=n;nw++){
sum+=a[nw];num++;
if(sum>=mid*num){
flag=true;
break;
}
}
if(!flag)return false;
for(nw++;nw<=n;nw++){
if(a[nw]>=mid||sum+a[nw]<mid*(num+1))break;
sum+=a[nw];num++;
}
cnt++;
}
if(nw>n)return false;
double sum=0,num=0;
for(;nw<=n;nw++){
sum+=a[nw];num++;
}
return sum>=num*mid;
}
int main() {
// freopen("2.in", "r", stdin);
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
double l = 0.0, r = 1e9, ans = 0.0;
while (l < r) {
double mid = (l + r) / 2.0;
if (check(mid)) {
ans = mid;
l = mid;
} else r = mid;
}
cout << ans;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
7 3 1 3 1 2 2 2 1