QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#442377 | #8524. Weather Forecast | ucup-team3282# | WA | 0ms | 3840kb | C++14 | 1.6kb | 2024-06-15 11:28:40 | 2024-06-15 11:28:40 |
Judging History
answer
#include <bits/stdc++.h>
#define eps 1e-9
using namespace std;
const int N = 2e5+9;
int n, k;
double a[N];
bool check(double mid) {
// cout<<mid<<":\n";
int nw=1,cnt=0;
while(cnt<k-1){
// cout<<cnt<<"?" ;
// cout<<nw<<"->";
double sum=0,num=0;
bool flag=false;
for(;nw<=n;nw++){
sum+=a[nw];num++;
if(sum>mid*num){
flag=true;
break;
}
}
// cout<<nw<<endl;
if(!flag)return false;
for(nw++;nw<=n;nw++){
if(a[nw]>mid||sum+a[nw]<mid*(num+1))break;
// cout<<"extent"<<nw<<endl;
sum+=a[nw];num++;
}
cnt++;
// nw++;
// cout<<nw-1<<endl;
}
// cout<<nw<<endl;
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;
// cout << check(1.6) << "[[[[]";
while (l + eps < r) {
double mid = (l + r) / 2;
if (check(mid)) {
ans = mid;
l = mid;
} else r = mid;
}
cout << ans;
return 0;
}
/*
// cout << mid << "----------------" <<endl;
double cur = 0; int l = 1; double sum = 0;int cc = 0, ans = 0;
while (l <= n && ans < k-1) {
cur = 0;sum = 0;
while (cur < mid && l <= n) {
sum += a[l];
l++; cc++;
cur = (double) (sum / cc);
}
if (l > n) break;
while (cur > mid && a[l] < mid && l<=n) {
sum += a[l];
l++; cc++;
cur = double (sum / cc);
}
cc = 0;
ans++;
// cout<<l-1<<endl;}
if(l>n)return false;
if (cur < mid) return false;
cur = 0;sum = 0;
for(;l<=n;l++){
cc++,sum+=a[l];
}
return sum/cc>=mid;
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3840kb
input:
7 3 1 3 1 2 2 2 1
output:
0
result:
wrong answer 1st numbers differ - expected: '1.66667', found: '0.00000', error = '1.66667'