QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#131871 | #5125. Adjusted Average | PetroTarnavskyi# | WA | 313ms | 3848kb | C++17 | 1.8kb | 2023-07-28 17:28:45 | 2023-07-28 17:28:47 |
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, vector<LL> a){
LL sum = 0;
FOR(i, 0, n){
a[i] -= x;
sum += a[i];
}
if(sum < 0){
FOR(i, 0, n)
a[i] *= -1;
sum *= -1;
}
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;
vector<LL> 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: 3828kb
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: 3704kb
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: 3824kb
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: 0ms
memory: 3636kb
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: 3644kb
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: 3704kb
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: 0ms
memory: 3828kb
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: 0ms
memory: 3652kb
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: 1ms
memory: 3644kb
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: 3832kb
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: 3748kb
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: 1ms
memory: 3772kb
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: 1ms
memory: 3644kb
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: 3748kb
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: 3828kb
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: 3640kb
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: 1ms
memory: 3644kb
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: 3744kb
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: 3596kb
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: 0
Accepted
time: 313ms
memory: 3848kb
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:
597654934.9678714275
result:
ok found '597654934.96787', expected '597654934.96787', error '0.00000'
Test #22:
score: 0
Accepted
time: 311ms
memory: 3844kb
input:
1000 4 -520031192 -828928297 -939974056 -890063527 -821483207 202331771 452507962 -984471175 730065137 -788464067 -814085288 -308486435 -251817293 982579015 -779352535 417038541 664276772 822475842 509497915 -536596860 616913996 358016799 -839048180 358771449 -538531644 562815966 635875550 337992251...
output:
558582928.1375502348
result:
ok found '558582928.13755', expected '558582928.13755', error '0.00000'
Test #23:
score: 0
Accepted
time: 1ms
memory: 3832kb
input:
5 3 78 -68 42 -52 42 50
output:
32.0000000000
result:
ok found '32.00000', expected '32.00000', error '0.00000'
Test #24:
score: 0
Accepted
time: 1ms
memory: 3772kb
input:
5 4 0 11 7 -13 -3 -6
output:
0.2500000000
result:
ok found '0.25000', expected '0.25000', error '0.00000'
Test #25:
score: 0
Accepted
time: 1ms
memory: 3700kb
input:
6 4 50483269 -812901056 614642221 945836657 -616198107 598529790 -614398526
output:
15984531.5000000000
result:
ok found '15984531.50000', expected '15984531.50000', error '0.00000'
Test #26:
score: 0
Accepted
time: 1ms
memory: 3828kb
input:
5 4 4 8 20 -18 3 9
output:
0.3333333333
result:
ok found '0.33333', expected '0.33333', error '0.00000'
Test #27:
score: 0
Accepted
time: 1ms
memory: 3652kb
input:
10 4 -472189650 -763683851 291512773 236754835 367611187 -650471393 -435169974 -783816043 -891608557 997972439 910540713
output:
36488132.5000000000
result:
ok found '36488132.50000', expected '36488132.50000', error '0.00000'
Test #28:
score: 0
Accepted
time: 1ms
memory: 3640kb
input:
6 4 -286216652 -146841360 -702906210 328658776 -159898481 154871206 -736124545
output:
2794288.0000000000
result:
ok found '2794288.00000', expected '2794288.00000', error '0.00000'
Test #29:
score: 0
Accepted
time: 209ms
memory: 3616kb
input:
1500 3 1 -3 -1 3 -1 1 -3 0 -2 -2 1 0 0 2 1 2 0 -2 -3 0 3 3 1 -2 0 1 2 0 0 -1 3 1 2 -1 0 -3 0 0 -2 -1 -3 2 3 0 0 3 -3 -3 -3 0 -3 0 2 -2 -2 3 -1 2 3 1 -2 -1 -2 -1 0 0 -2 2 2 2 -2 2 -1 3 -2 2 -3 -3 2 -2 3 -2 -1 2 -1 1 1 0 0 3 -3 3 -2 -2 -3 3 0 0 -3 2 -1 -2 1 2 0 0 3 0 1 3 2 -1 3 -1 1 -3 1 -2 1 -1 3 2 0...
output:
0.9719438878
result:
ok found '0.97194', expected '0.97194', error '0.00000'
Test #30:
score: 0
Accepted
time: 311ms
memory: 3764kb
input:
1000 4 0 -5 3 4 4 2 -2 -1 -3 -4 -1 2 -2 1 -3 4 0 -1 -5 -2 2 2 4 -2 -1 -2 -1 -2 -4 1 -1 3 -4 2 -1 -3 2 5 2 -1 -1 -1 -2 5 -5 0 -1 -4 3 5 0 3 2 -4 5 -3 -2 5 -1 -1 -3 -3 2 2 3 -3 1 5 2 -4 4 1 5 -5 -4 5 -2 -4 2 -4 1 0 -5 1 -4 1 1 -2 -4 5 4 -2 -4 1 -4 -5 3 -1 5 -4 -4 -5 -1 -2 -2 -1 -2 -5 2 5 3 -4 -1 1 3 5...
output:
0.0090361446
result:
ok found '0.00904', expected '0.00904', error '0.00000'
Test #31:
score: 0
Accepted
time: 1ms
memory: 3748kb
input:
10 4 -652315249 248814082 -310330977 -7639307 -808957195 -937992709 -461255220 526406959 317472565 958347317 -387890815
output:
166637545.1666666567
result:
ok found '166637545.16667', expected '166637545.16667', error '0.00000'
Test #32:
score: 0
Accepted
time: 1ms
memory: 3700kb
input:
6 4 802938834 279940040 -341612005 -603412852 781046065 -36716272 116954057
output:
272445781.5000000000
result:
ok found '272445781.50000', expected '272445781.50000', error '0.00000'
Test #33:
score: 0
Accepted
time: 1ms
memory: 3664kb
input:
20 4 221873446 849467103 884117952 312351432 -736878277 -296631326 -653303218 924111525 705904846 927004812 -810297249 860376579 744928549 -85282366 -877593960 698190037 840265628 -392839463 828364237 -422208014 198779260
output:
17181.1666666667
result:
ok found '17181.16667', expected '17181.16667', error '0.00000'
Test #34:
score: -100
Wrong Answer
time: 1ms
memory: 3648kb
input:
15 4 275628638 -847206183 782559411 141146580 425437384 810109824 -265811904 668678866 900016918 -401762002 358260741 574537650 -352457220 -504612680 418460859 909853096
output:
354545.3333333333
result:
wrong answer 1st numbers differ - expected: '125105.00000', found: '354545.33333', error = '1.83398'