Submission #330904

#	Time	Username	Problem	Language	Result	Execution time	Memory
330904		CodeTiger927	Simfonija (COCI19_simfonija)	C++14	110 / 110	105 ms	5996 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;
	int sec = K;
	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()] - i - 1;
			sum -= i + 1 - arr[ptr++];
			inc--;
			s.pop();
		}
		ans = min(ans,sum);
	}
	cout << ans << endl;
}

Compilation message (stderr)

simfonija.cpp: In function 'int main()':
simfonija.cpp:34:6: warning: unused variable 'sec' [-Wunused-variable]
   34 |  int sec = K;
      |      ^~~

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