oj.uz

Submission #208672

# Submission time Handle Problem Language Result Execution time Memory
208672 2020-03-12T01:46:39 Z bensonlzl Simfonija (COCI19_simfonija) C++14
110 / 110
 106 ms 13588 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 376 KB Output is correct

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 4468 KB Output is correct
2 Correct 42 ms 4468 KB Output is correct
3 Correct 34 ms 4468 KB Output is correct

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 4596 KB Output is correct
2 Correct 50 ms 4444 KB Output is correct
3 Correct 34 ms 4468 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 4468 KB Output is correct
2 Correct 40 ms 4516 KB Output is correct
3 Correct 38 ms 4496 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 12880 KB Output is correct
2 Correct 99 ms 13464 KB Output is correct
3 Correct 94 ms 13552 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 13552 KB Output is correct
2 Correct 103 ms 13532 KB Output is correct
3 Correct 88 ms 13588 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 13448 KB Output is correct
2 Correct 74 ms 13552 KB Output is correct
3 Correct 94 ms 13508 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 13552 KB Output is correct
2 Correct 96 ms 13548 KB Output is correct
3 Correct 79 ms 13548 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 13552 KB Output is correct
2 Correct 106 ms 13548 KB Output is correct
3 Correct 60 ms 13552 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 13552 KB Output is correct
2 Correct 57 ms 13528 KB Output is correct
3 Correct 72 ms 13524 KB Output is correct