Submission #330903

#	Time	Username	Problem	Language	Result	Execution time	Memory
330903		CodeTiger927	Simfonija (COCI19_simfonija)	C++14	44 / 110	106 ms	5740 KiB

simfonija

using namespace std;

#include <iostream>
#include <stack>
#include <algorithm>

#define MAXN 100005

int counter[4000005],A[MAXN],B[MAXN],arr[MAXN],N,K;

int main() {
	cin >> N >> K;
	long long sum = 0;
	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) {
		arr[i] = A[i] - B[i] + 2000001;
		counter[arr[i]]++;
		sum += arr[i];
	}
	sort(arr,arr + N);
	stack<int> s;
	for(int i = 0;i < K;++i) {
		s.push(N - i - 1);
		sum -= arr[N - i - 1];
	}
	long long ans = sum;
	int inc = 0;
	int ptr = 0;
	for(int i = 0;i < 4000005;++i) {
		inc += counter[i];
		sum += inc - (N - K - inc);

		while(!s.empty() && (arr[s.top()] - i - 1) < (i + 1 - arr[ptr])) {
			sum += arr[s.top()] - arr[ptr++] - 2 * i - 2;
			inc--;
			s.pop();
		}
		ans = min(ans,sum);
	}
	cout << ans << endl;
}

• 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