oj.uz

Submission #101844

# Submission time Handle Problem Language Result Execution time Memory
101844 2019-03-20T13:56:16 Z Ort Simfonija (COCI19_simfonija) C++11
44 / 110
 170 ms 4216 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 = n-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 3 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 161 ms 4088 KB Output is correct
2 Correct 131 ms 4088 KB Output is correct
3 Correct 94 ms 4160 KB Output is correct

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 4100 KB Output is correct
2 Correct 136 ms 4088 KB Output is correct
3 Correct 95 ms 4112 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 4136 KB Output is correct
2 Correct 136 ms 4088 KB Output is correct
3 Correct 95 ms 4088 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 3448 KB Output is correct
2 Correct 83 ms 4088 KB Output is correct
3 Incorrect 122 ms 4216 KB Output isn't correct

Subtask #6
0 / 11.0

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

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 4088 KB Output is correct
2 Incorrect 106 ms 4088 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

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

Subtask #9
0 / 11.0

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

Subtask #10
0 / 11.0

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