QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#131869#5125. Adjusted AveragePetroTarnavskyi#WA 279ms3852kbC++171.8kb2023-07-28 17:24:082023-07-28 17:24:12

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-28 17:24:12]
  • 评测
  • 测评结果:WA
  • 用时:279ms
  • 内存:3852kb
  • [2023-07-28 17:24:08]
  • 提交

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'