oj.uz

Submission #330904

# Submission time Handle Problem Language Result Execution time Memory
330904 2020-11-26T21:01:21 Z CodeTiger927 Simfonija (COCI19_simfonija) C++14
110 / 110
 105 ms 5996 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;
	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

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

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 492 KB Output is correct
3 Correct 21 ms 364 KB Output is correct

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 5484 KB Output is correct
2 Correct 90 ms 3052 KB Output is correct
3 Correct 88 ms 1644 KB Output is correct

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 5484 KB Output is correct
2 Correct 101 ms 3052 KB Output is correct
3 Correct 88 ms 1644 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 5484 KB Output is correct
2 Correct 90 ms 3052 KB Output is correct
3 Correct 88 ms 1644 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 1772 KB Output is correct
2 Correct 89 ms 1900 KB Output is correct
3 Correct 91 ms 2156 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 5484 KB Output is correct
2 Correct 97 ms 5868 KB Output is correct
3 Correct 97 ms 5740 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 1900 KB Output is correct
2 Correct 90 ms 2028 KB Output is correct
3 Correct 97 ms 5868 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 5612 KB Output is correct
2 Correct 90 ms 2156 KB Output is correct
3 Correct 105 ms 5740 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 5612 KB Output is correct
2 Correct 98 ms 5996 KB Output is correct
3 Correct 96 ms 5612 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 1900 KB Output is correct
2 Correct 90 ms 1900 KB Output is correct
3 Correct 99 ms 5612 KB Output is correct