oj.uz

Submission #330903

# Submission time Handle Problem Language Result Execution time Memory
330903 2020-11-26T21:00:52 Z CodeTiger927 Simfonija (COCI19_simfonija) C++14
44 / 110
 106 ms 5740 KB 
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.0 / 11.0

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

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 5612 KB Output is correct
2 Correct 92 ms 3148 KB Output is correct
3 Correct 89 ms 1752 KB Output is correct

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 5612 KB Output is correct
2 Correct 98 ms 3308 KB Output is correct
3 Correct 91 ms 1772 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 5612 KB Output is correct
2 Correct 93 ms 3180 KB Output is correct
3 Correct 101 ms 1772 KB Output is correct

Subtask #5
0 / 11.0

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

Subtask #6
0 / 11.0

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

Subtask #7
0 / 11.0

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

Subtask #8
0 / 11.0

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

Subtask #9
0 / 11.0

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

Subtask #10
0 / 11.0

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