Submission #101847

#	Time	Username	Problem	Language	Result	Execution time	Memory
101847		Ort	Simfonija (COCI19_simfonija)	C++11	44 / 110	162 ms	2808 KiB

simfonija

#include<iostream>
#include<algorithm>
#include<vector>
#define MAX 100010
#define ll long long

using namespace std;

int a[MAX], b[MAX];

ll n, k, sol = 1000000000000000;
vector<ll> diff;

bool process(int x) {
	int pos = 0, neg = 0; ll sum = 0;
	vector<ll> f(n);
	for(int i=0;i<n;i++) {
		f[i] = abs(a[i]+x-b[i]);
		if((a[i]+x-b[i])<0) neg++;
		if((a[i]+x-b[i])>0) pos++;
	}
	sort(f.begin(),f.end());
	for(int i=0;i<n-k;i++) sum += f[i];
	sol = min(sol, sum);
	return (neg>=pos);
}

int main() {
	cin.sync_with_stdio(0); cin.tie(0);
	cin.exceptions(cin.failbit);
	cin >> n >> k; diff.resize(n);
	for(int i=0;i<n;i++) cin >> a[i];
	for(int i=0;i<n;i++) cin >> b[i];
	for(int i=0;i<n;i++) diff[i] = (b[i]-a[i]);
	sort(diff.begin(),diff.end());
	diff.erase( unique( diff.begin(), diff.end() ), diff.end() );
	int low = 0, high = diff.size()-1;
	while(high-low>1) {
		int mid = (high+low)/2;
		if(process(diff[mid])) low = mid;
		else high = mid;	
	}
	cout << sol;
	return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 0 / 11
• Subtask 6: 0 / 11
• Subtask 7: 0 / 11
• Subtask 8: 0 / 11
• Subtask 9: 0 / 11
• Subtask 10: 0 / 11