oj.uz

Submission #200100

# Submission time Handle Problem Language Result Execution time Memory
200100 2020-02-05T10:24:16 Z Saboon Simfonija (COCI19_simfonija) C++14
110 / 110
 43 ms 3448 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;

const int maxn = 1e5 + 10;

ll par[maxn], a[maxn];

ll cost(int l, int r){
	int median = (l + r) >> 1;
	return a[median] * (median - l + 1) - (par[median] - par[l - 1]) + 
		(par[r] - par[median]) - a[median] * (r - median);
}

int main(){
	ios_base::sync_with_stdio(false);
	int n, k;
	cin >> n >> k;
	k = n - k;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= n; i++){
		int x;
		cin >> x;
		a[i] -= x;
	}
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; i++)
		par[i] = par[i - 1] + a[i];

	ll answer = 1000ll * 1000 * 1000 * 1000;
	for (int l = 1; l <= n - k + 1; l++){
		int r = l + k - 1;
		answer = min(answer, cost(l, r));
	}
	cout << answer << endl;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 3296 KB Output is correct
2 Correct 42 ms 3324 KB Output is correct
3 Correct 35 ms 3320 KB Output is correct

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 3320 KB Output is correct
2 Correct 38 ms 3320 KB Output is correct
3 Correct 36 ms 3320 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 3320 KB Output is correct
2 Correct 38 ms 3320 KB Output is correct
3 Correct 43 ms 3320 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2680 KB Output is correct
2 Correct 37 ms 3320 KB Output is correct
3 Correct 38 ms 3320 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 3320 KB Output is correct
2 Correct 42 ms 3448 KB Output is correct
3 Correct 42 ms 3320 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 3336 KB Output is correct
2 Correct 39 ms 3320 KB Output is correct
3 Correct 40 ms 3320 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 3320 KB Output is correct
2 Correct 37 ms 3296 KB Output is correct
3 Correct 41 ms 3320 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 3448 KB Output is correct
2 Correct 43 ms 3320 KB Output is correct
3 Correct 41 ms 3320 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 3320 KB Output is correct
2 Correct 41 ms 3320 KB Output is correct
3 Correct 41 ms 3344 KB Output is correct