oj.uz

Submission #330897

# Submission time Handle Problem Language Result Execution time Memory
330897 2020-11-26T20:47:01 Z CodeTiger927 Simfonija (COCI19_simfonija) C++14
110 / 110
 115 ms 7276 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--;
			// cout << i << " " << s.top() << " " << (ptr - 1) << " " << sum << endl;
			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 21 ms 364 KB Output is correct
2 Correct 18 ms 364 KB Output is correct
3 Correct 20 ms 364 KB Output is correct

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 6892 KB Output is correct
2 Correct 96 ms 4460 KB Output is correct
3 Correct 90 ms 3052 KB Output is correct

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 6892 KB Output is correct
2 Correct 93 ms 4460 KB Output is correct
3 Correct 95 ms 3180 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 6892 KB Output is correct
2 Correct 92 ms 4504 KB Output is correct
3 Correct 88 ms 3052 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 2668 KB Output is correct
2 Correct 90 ms 3308 KB Output is correct
3 Correct 91 ms 3436 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 7020 KB Output is correct
2 Correct 97 ms 7276 KB Output is correct
3 Correct 115 ms 7148 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 3308 KB Output is correct
2 Correct 93 ms 3308 KB Output is correct
3 Correct 97 ms 7148 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 7148 KB Output is correct
2 Correct 92 ms 3436 KB Output is correct
3 Correct 97 ms 7020 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 7068 KB Output is correct
2 Correct 98 ms 7276 KB Output is correct
3 Correct 103 ms 6892 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 3416 KB Output is correct
2 Correct 93 ms 3180 KB Output is correct
3 Correct 97 ms 7020 KB Output is correct