oj.uz

Submission #463476

# Submission time Handle Problem Language Result Execution time Memory
463476 2021-08-11T08:18:46 Z grt Simfonija (COCI19_simfonija) C++17
110 / 110
 38 ms 2992 KB 
#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second
#define _ ios_base::sync_with_stdio(0); cin.tie(0);
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

using namespace std;

using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

const int nax = 100 * 1000 + 10;
const ll INF = 1e18;
int a[nax], n, k;
ll sum[nax];

int main() {_
	cin >> n >> k;
	for(int i = 1; i <= n; ++i) {
		cin >> a[i];
	}
	for(int x, i = 1; i <= n; ++i) {
		cin >> x;
		a[i] -= x;
	}
	sort(a + 1, a + n + 1);
	for(int i = 1; i <= n; ++i) {
		sum[i] = sum[i - 1] + a[i];
	}
	int m = (n - k - 1) / 2 + 1;
	ll ans = (ll)a[m] * (m - 1) - sum[m - 1] + sum[n - k] - sum[m] - (ll)a[m]*(n - k - m);
	for(int i = 1; i <= k; ++i) {
		m++;
		ans = min(ans, (ll)a[m] * (m - 1 - i) - (sum[m - 1] - sum[i]) + sum[n - k + i] - sum[m] - (ll)a[m]*(n - k - m + i));
	}
	cout << ans;
	
}

Subtask #1
11.0 / 11.0

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

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2908 KB Output is correct
2 Correct 35 ms 2852 KB Output is correct
3 Correct 34 ms 2872 KB Output is correct

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 2892 KB Output is correct
2 Correct 29 ms 2868 KB Output is correct
3 Correct 27 ms 2868 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 2864 KB Output is correct
2 Correct 36 ms 2864 KB Output is correct
3 Correct 33 ms 2872 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2116 KB Output is correct
2 Correct 27 ms 2832 KB Output is correct
3 Correct 28 ms 2884 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 2872 KB Output is correct
2 Correct 32 ms 2884 KB Output is correct
3 Correct 38 ms 2992 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 2864 KB Output is correct
2 Correct 28 ms 2788 KB Output is correct
3 Correct 31 ms 2892 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 2884 KB Output is correct
2 Correct 28 ms 2864 KB Output is correct
3 Correct 38 ms 2868 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2864 KB Output is correct
2 Correct 35 ms 2884 KB Output is correct
3 Correct 33 ms 2904 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2916 KB Output is correct
2 Correct 34 ms 2852 KB Output is correct
3 Correct 32 ms 2908 KB Output is correct