Submission #200100

#	Time	Username	Problem	Language	Result	Execution time	Memory
200100		Saboon	Simfonija (COCI19_simfonija)	C++14	110 / 110	43 ms	3448 KiB

simfonija

#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 / 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