oj.uz

Submission #101847

# Submission time Handle Problem Language Result Execution time Memory
101847 2019-03-20T14:00:16 Z Ort Simfonija (COCI19_simfonija) C++11
44 / 110
 162 ms 2808 KB 
#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.0 / 11.0

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

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 2712 KB Output is correct
2 Correct 84 ms 2708 KB Output is correct
3 Correct 44 ms 2688 KB Output is correct

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 2796 KB Output is correct
2 Correct 86 ms 2680 KB Output is correct
3 Correct 42 ms 2680 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 2656 KB Output is correct
2 Correct 81 ms 2680 KB Output is correct
3 Correct 41 ms 2680 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 2680 KB Output is correct
2 Correct 46 ms 2680 KB Output is correct
3 Incorrect 52 ms 2756 KB Output isn't correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 152 ms 2808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 2808 KB Output is correct
2 Incorrect 62 ms 2640 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 162 ms 2744 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 117 ms 2728 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 2808 KB Output isn't correct
2 Halted 0 ms 0 KB -