QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#131869 | #5125. Adjusted Average | PetroTarnavskyi# | WA | 279ms | 3852kb | C++17 | 1.8kb | 2023-07-28 17:24:08 | 2023-07-28 17:24:12 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define MP make_pair
#define PB push_back
#define F first
#define S second
#define FILL(a, b) memset(a, b, sizeof(a))
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef long double db;
long double solve(int n, int k, int x, VI a){
LL sum = 0;
FOR(i, 0, n)
sum += a[i];
if(sum < 1LL * x * (n - k)){
FOR(i, 0, n)
a[i] *= -1;
x *= -1;
sum *= -1;
}
sum -= 1LL * x * (n - k);
sort(ALL(a));
LL mn = sum;
if(k == 0)
mn = sum;
if(k == 1){
FOR(i, 0, n)
mn = min(mn, abs(sum - a[i]));
}
if(k == 2){
FOR(i, 0, n)
FOR(j, i + 1, n)
mn = min(mn, abs(sum - a[i] - a[j]));
}
if(k == 3){
FOR(i, 0, n)
FOR(j, i + 1, n)
FOR(z, j + 1, n)
mn = min(mn, abs(sum - a[i] - a[j] - a[z]));
}
if(k == 4){
FOR(i, 0, n - 3)
FOR(j, i + 1, n - 2){
int z = j + 1;
LL cur = a[i] + a[j] + a[z];
int pos = n - 1;
while(z < n){
while(pos > z && a[pos] + cur > sum)
pos--;
if(pos + 1 != n)
mn = min(mn, a[pos + 1] + cur - sum);
if(pos == z)
break;
mn = min(mn, sum - a[pos] - cur);
z++;
}
}
}
return 1.0 * mn / (n - k);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, k, x;
cin >> n >> k >> x;
VI a(n);
FOR(i, 0, n)
cin >> a[i];
db ans = solve(n, 0, x, a);
FOR(i, 1, k + 1)
ans = min(ans, solve(n, i, x, a));
cout << fixed << setprecision(10) << ans << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3652kb
input:
5 2 2 1 2 3 100 200
output:
0.0000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3648kb
input:
5 4 -5 -6 -3 0 6 3
output:
0.5000000000
result:
ok found '0.50000', expected '0.50000', error '0.00000'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3644kb
input:
4 1 4 1 3 3 7
output:
0.3333333333
result:
ok found '0.33333', expected '0.33333', error '0.00000'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3732kb
input:
2 1 0 0 0
output:
0.0000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3740kb
input:
2 1 1 2 3
output:
1.0000000000
result:
ok found '1.00000', expected '1.00000', error '0.00000'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3648kb
input:
4 1 0 -2 -1 1 2
output:
0.0000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3832kb
input:
5 2 0 -1 2 3 -4 42
output:
0.0000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3752kb
input:
6 2 0 -5 -1 1 3 3 5
output:
0.0000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
5 4 -1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
output:
2000000000.0000000000
result:
ok found '2000000000.00000', expected '2000000000.00000', error '0.00000'
Test #10:
score: 0
Accepted
time: 1ms
memory: 3744kb
input:
5 4 1000000000 -1000000000 -1000000000 -1000000000 -1000000000 -1000000000
output:
2000000000.0000000000
result:
ok found '2000000000.00000', expected '2000000000.00000', error '0.00000'
Test #11:
score: 0
Accepted
time: 1ms
memory: 3696kb
input:
5 1 0 -16 -12 4 12 20
output:
1.0000000000
result:
ok found '1.00000', expected '1.00000', error '0.00000'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3752kb
input:
8 2 0 -18 -6 -6 0 0 24 36 42
output:
1.0000000000
result:
ok found '1.00000', expected '1.00000', error '0.00000'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
5 1 0 10000 -10 -100 -1000 -3900
output:
998.0000000000
result:
ok found '998.00000', expected '998.00000', error '0.00000'
Test #14:
score: 0
Accepted
time: 1ms
memory: 3640kb
input:
15 3 1 -3 3 0 -3 3 2 0 3 -1 -1 0 -3 1 -1 -2
output:
0.4166666667
result:
ok found '0.41667', expected '0.41667', error '0.00000'
Test #15:
score: 0
Accepted
time: 1ms
memory: 3644kb
input:
6 1 0 -1 -1 -1 1 1 1
output:
0.0000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #16:
score: 0
Accepted
time: 1ms
memory: 3776kb
input:
8 1 80 -90 52 -98 -79 70 86 38 -77
output:
80.0000000000
result:
ok found '80.00000', expected '80.00000', error '0.00000'
Test #17:
score: 0
Accepted
time: 1ms
memory: 3772kb
input:
5 3 37 3 72 88 23 -51
output:
0.5000000000
result:
ok found '0.50000', expected '0.50000', error '0.00000'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
8 3 -50 -68 -98 34 55 -9 83 -64 -45
output:
1.8000000000
result:
ok found '1.80000', expected '1.80000', error '0.00000'
Test #19:
score: 0
Accepted
time: 1ms
memory: 3700kb
input:
5 2 62 -21 82 9 65 94
output:
0.3333333333
result:
ok found '0.33333', expected '0.33333', error '0.00000'
Test #20:
score: 0
Accepted
time: 1ms
memory: 3648kb
input:
10 4 -16 57 60 25 -60 -31 -70 25 -45 -8 -93
output:
0.0000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #21:
score: -100
Wrong Answer
time: 279ms
memory: 3852kb
input:
1000 4 -589682264 239898913 202060748 -888127376 -880309095 124799170 -494539478 -745680608 726341697 992941811 -992809843 -977069412 -627162219 -243367314 325137914 647494705 994977955 32926705 618107495 702088915 19011397 546487463 811676912 -599600278 178857199 475002521 -328010873 568834738 -650...
output:
598501333.8684738874
result:
wrong answer 1st numbers differ - expected: '597654934.96787', found: '598501333.86847', error = '0.00142'