oj.uz

Submission #357575

# Submission time Handle Problem Language Result Execution time Memory
357575 2021-01-24T06:54:17 Z ijxjdjd Simfonija (COCI19_simfonija) C++14
110 / 110
 76 ms 3560 KB 
#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
using namespace std;

using ll = long long;

int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);
	int N;
	int K;
	cin >> N >> K;
	deque<int> farleft;
	ll sumfarleft = 0;
	deque<int> left;
	ll sumleft = 0;
	deque<int> right;
	ll sumright = 0;
	deque<int> farright;
	ll sumfarright = 0;
	int A[N];
	int B[N];
	int X = (int)(1e6)+1;
//	int X = 0;
	vector<int> diff;
	FR(i, N) {
        cin >> A[i];
        A[i] -= X;
	}
	FR(i, N) {
        cin >> B[i];
        diff.push_back(A[i] - B[i]);
	}
	sort(diff.begin(), diff.end());
	FR(i, K) {
        farleft.push_back(diff[i]);
        sumfarleft += -diff[i];
	}
	for (int i = K; i < N; i++) {
        left.push_back(diff[i]);
        sumleft += -diff[i];
	}
	ll ans = ll(1e18);
	for (int i = 1; i <= 2*X; i++) {
        ans = min(ans, sumleft + sumright);
        sumleft -= left.size();
        sumfarleft -= farleft.size();
        sumright += right.size();
        sumfarright += farright.size();
        while (left.size() > 0 && (left.back()) == -i) {
            left.pop_back();
            right.push_front(-i);
        }
        while (farleft.size() > 0 && (farleft.back()) == -i) {
            farleft.pop_back();
            right.push_front(-i);
        }
        while (right.size() > 0 && farleft.size() > 0 && (-(farleft.back()+i) < right.back()+i)) {
            left.push_front(farleft.back());
            sumleft += -(farleft.back() + i);
            sumfarleft -= -(farleft.back() + i);
            farleft.pop_back();
            farright.push_front(right.back());
            sumright -= right.back() + i;
            sumfarright += right.back() + i;
            right.pop_back();
        }
        while (farleft.size() + farright.size() < K) {
            farright.push_front(right.back());
            sumfarright += right.back() + i;
            sumright -= right.back() + i;
            right.pop_back();
        }
	}
	cout << ans << '\n';
	return 0;
}

Compilation message

simfonija.cpp: In function 'int main()':
simfonija.cpp:68:49: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   68 |         while (farleft.size() + farright.size() < K) {
      |                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 364 KB Output is correct
2 Correct 28 ms 492 KB Output is correct
3 Correct 29 ms 364 KB Output is correct

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 3432 KB Output is correct
2 Correct 53 ms 3344 KB Output is correct
3 Correct 51 ms 3432 KB Output is correct

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 3432 KB Output is correct
2 Correct 55 ms 3432 KB Output is correct
3 Correct 51 ms 3432 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 3432 KB Output is correct
2 Correct 53 ms 3432 KB Output is correct
3 Correct 51 ms 3304 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 2792 KB Output is correct
2 Correct 56 ms 3336 KB Output is correct
3 Correct 62 ms 3432 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 3432 KB Output is correct
2 Correct 76 ms 3560 KB Output is correct
3 Correct 69 ms 3432 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 3412 KB Output is correct
2 Correct 54 ms 3428 KB Output is correct
3 Correct 58 ms 3432 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 3432 KB Output is correct
2 Correct 55 ms 3432 KB Output is correct
3 Correct 59 ms 3432 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 3432 KB Output is correct
2 Correct 62 ms 3432 KB Output is correct
3 Correct 58 ms 3432 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 3432 KB Output is correct
2 Correct 53 ms 3432 KB Output is correct
3 Correct 58 ms 3432 KB Output is correct