QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#442387 | #8524. Weather Forecast | ucup-team3282# | WA | 1ms | 3960kb | C++14 | 1.4kb | 2024-06-15 11:33:37 | 2024-06-15 11:33:38 |
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) {
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++;
}
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 + eps < r) {
double mid = (l + r) / 2.0;
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: 100
Accepted
time: 1ms
memory: 3960kb
input:
7 3 1 3 1 2 2 2 1
output:
1.66667
result:
ok found '1.66667', expected '1.66667', error '0.00000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3852kb
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: 3816kb
input:
2 1 2 1
output:
1.5
result:
ok found '1.50000', expected '1.50000', error '0.00000'
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3800kb
input:
3 2 2 4 4
output:
3.33333
result:
wrong answer 1st numbers differ - expected: '3.00000', found: '3.33333', error = '0.33333'