Submission #208672

#	Time	Username	Problem	Language	Result	Execution time	Memory
208672		bensonlzl	Simfonija (COCI19_simfonija)	C++14	110 / 110	106 ms	13588 KiB

simfonija

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll N, K, A[100005], B[100005], tot = 0;

struct node{
	node *left = nullptr, *right = nullptr;
	int S, E;
	ll sum = 0;
	node(int _s, int _e){
		S = _s;
		E = _e;
		if (S == E) return;
		left = new node(S,(S+E)/2);
		right = new node((S+E)/2+1,E);
	}
	void update(int x, ll v){
		if (S == E){
			sum = v;
			return;
		}
		if (x <= (S+E)/2) left->update(x,v);
		else right->update(x,v);
		sum = left->sum + right->sum;
	}
	ll query(int l, int r){
		if (l > E || r < S) return 0;
		if (l <= S && E <= r) return sum;
		return left->query(l,r)+right->query(l,r);
	}
} *root;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> K;
	for (int i = 1; i <= N; ++i){
		cin >> A[i];
	}
	for (int i = 1; i <= N; ++i){
		cin >> B[i];
	}
	vector<ll> v;
	for (int i = 1; i <= N; ++i){
		v.push_back(A[i]-B[i]);
	}
	sort(v.begin(),v.end());
	if (K == N){
		cout << 0 << '\n';
		return 0;
	}
	else if (K == 0){
		
		ll x = v[N/2];
		for (int i = 1; i <= N; ++i){
			A[i] -= x;
		}
		for (int i = 1; i <= N; ++i){
			tot += abs(A[i]-B[i]);
		}
		cout << tot << '\n';
		return 0;
	}
	else{
		tot = 1e17;
		root = new node(0,N+1);
		deque<ll> dq;
		int middlept = 0;
		for (int i = 1; i <= N-K; ++i){
			root->update(i,v[i-1]);
		}
		middlept = (N-K)/2;
		for (int i = 0; i <= K; ++i){
			ll val = v[middlept];
			
			tot = min(tot,(middlept+1-i)*val-root->query(i+1,middlept+1)+root->query(middlept+2,i+N-K)-(i+N-K-middlept-1)*val);
			root->update(i+N-K+1,v[i+N-K]);
			middlept++;
		}
		cout << tot << '\n';
	}
}

• 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