Submission #463476

#	Time	Username	Problem	Language	Result	Execution time	Memory
463476		grt	Simfonija (COCI19_simfonija)	C++17	110 / 110	38 ms	2992 KiB

simfonija

#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 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 11 / 11
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 11 / 11
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11