Submission #357575

#	Time	Username	Problem	Language	Result	Execution time	Memory
357575		ijxjdjd	Simfonija (COCI19_simfonija)	C++14	110 / 110	76 ms	3560 KiB

simfonija

#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 (stderr)

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 / 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