oj.uz

Submission #115076

# Submission time Handle Problem Language Result Execution time Memory
115076 2019-06-05T07:08:34 Z MB81 Simfonija (COCI19_simfonija) C++14
110 / 110
 57 ms 4032 KB 
// 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.0 / 11.0

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

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 3828 KB Output is correct
2 Correct 41 ms 3828 KB Output is correct
3 Correct 38 ms 3956 KB Output is correct

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 3928 KB Output is correct
2 Correct 42 ms 3800 KB Output is correct
3 Correct 38 ms 3940 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 3828 KB Output is correct
2 Correct 42 ms 3796 KB Output is correct
3 Correct 38 ms 3828 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3188 KB Output is correct
2 Correct 35 ms 3828 KB Output is correct
3 Correct 43 ms 4032 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 4028 KB Output is correct
2 Correct 46 ms 3956 KB Output is correct
3 Correct 44 ms 3956 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 3828 KB Output is correct
2 Correct 42 ms 3828 KB Output is correct
3 Correct 45 ms 3908 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 3956 KB Output is correct
2 Correct 41 ms 3824 KB Output is correct
3 Correct 44 ms 3912 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 3828 KB Output is correct
2 Correct 57 ms 3828 KB Output is correct
3 Correct 42 ms 3828 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 4016 KB Output is correct
2 Correct 41 ms 3912 KB Output is correct
3 Correct 45 ms 3956 KB Output is correct