Submission #115076

#	Time	Username	Problem	Language	Result	Execution time	Memory
115076		MB81	Simfonija (COCI19_simfonija)	C++14	110 / 110	57 ms	4032 KiB

simfonija

// arara
#include <bits/stdc++.h>

using namespace std;
typedef long long int64;
typedef pair<int,int> pii;
typedef pair<int64,int> pii32;
typedef pair<int64,int64> pii64;

#define PB push_back
#define MP make_pair
#define F first
#define S second
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()

const int maxn = 1e5+10;
const int64 MO = 1e9+7;
const int64 IN = 1e18;

vector <int> v1;
int64 pr[maxn];
int a[maxn], b[maxn];
int n, k;

bool cmp (int x, int y) {
	if (a[x] - b[x] < a[y] - b[y])
		return 1;
	if (a[x] - b[x] > a[y] - b[y])
		return 0;
	return (x < y);
}

int64 sum (int idx) {
	if (idx < 0)
		return 0;
	return pr[idx];
}

int main () {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		v1.PB(i);
	}
	for (int i = 0; i < n; i++)
		cin >> b[i];
	int64 ans = IN;
	int pos = n;
	sort(all(v1), cmp);
	for (int i = 0; i < n; i++)
		if (a[v1[i]] - b[v1[i]] >= 0) {
			pos = i;
			break;
		}
	pr[0] = abs(a[v1[0]] - b[v1[0]]);
	for (int i = 1; i < n; i++)
		pr[i] = pr[i - 1] + abs(a[v1[i]] - b[v1[i]]);
	for (int i = 0; i < n; i++) {
		int l, r;
		l = i - (n - k) / 2;
		r = i + (n - k) / 2 - (1 - (n - k) % 2);
		if (a[v1[i]] - b[v1[i]] >= 0 || l < 0 || r >= n)
			continue;
		int f = min(pos, r + 1);
		int64 val = b[v1[i]] - a[v1[i]]; 
		int64 cur = 0;
		cur += sum(i) - sum(l - 1) - val * ((n - k) / 2 + 1);
		cur += val * (f - i - 1) - sum(f - 1) + sum(i);
		if (f <= r)
			cur += sum(r) - sum(f - 1) + val * (r - f + 1);
		ans = min(ans, cur);
	}
	reverse(all(v1));
	pos = n;
	for (int i = 0; i < n; i++)
		if (a[v1[i]] - b[v1[i]] <= 0) {
			pos = i;
			break;
		}
	pr[0] = abs(a[v1[0]] - b[v1[0]]);
	for (int i = 1; i < n; i++)
		pr[i] = pr[i - 1] + abs(a[v1[i]] - b[v1[i]]);
	for (int i = 0; i < n; i++) {
		int l, r;
		l = i - (n - k) / 2;
		r = i + (n - k) / 2 - (1 - (n - k) % 2);
		if (a[v1[i]] - b[v1[i]] <= 0 || l < 0 || r >= n)
			continue;
		int f = min(pos, r + 1);
		int64 val = a[v1[i]] - b[v1[i]];
		int64 cur = 0;
		cur += sum(i) - sum(l - 1) - val * ((n - k) / 2 + 1);
		cur += val * (f - i - 1) - sum(f - 1) + sum(i);
		if (f <= r)
			cur += sum(r) - sum(f - 1) + val * (r - f + 1);
		ans = min(ans, cur);
	}
	cout << ans << "\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