oj.uz

Submission #101846

# Submission time Handle Problem Language Result Execution time Memory
101846 2019-03-20T13:57:44 Z Ort Simfonija (COCI19_simfonija) C++11
44 / 110
 169 ms 2844 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 141 ms 2724 KB Output is correct
2 Correct 83 ms 2680 KB Output is correct
3 Correct 39 ms 2680 KB Output is correct

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 2680 KB Output is correct
2 Correct 94 ms 2652 KB Output is correct
3 Correct 43 ms 2680 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 2652 KB Output is correct
2 Correct 78 ms 2680 KB Output is correct
3 Correct 39 ms 2732 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 2680 KB Output is correct
2 Correct 40 ms 2680 KB Output is correct
3 Incorrect 56 ms 2672 KB Output isn't correct

Subtask #6
0 / 11.0

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

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 2684 KB Output is correct
2 Incorrect 54 ms 2652 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

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

Subtask #9
0 / 11.0

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

Subtask #10
0 / 11.0

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