Submission #105066

#	Time	Username	Problem	Language	Result	Execution time	Memory
105066		polyfish	Simfonija (COCI19_simfonija)	C++14	110 / 110	48 ms	4216 KiB

simfonija

//Pantyhose(black) + glasses = infinity

#include <bits/stdc++.h>
using namespace std;
 
#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "sol"

const int MAX_N = 100002;
const int64_t INF = 1e18;

int n, k, a[MAX_N], b[MAX_N];
int64_t p[MAX_N], ps[MAX_N];

void read_input() {
	cin >> n >> k;
	k = n - k;

	for (int i=1; i<=n; ++i)
		cin >> a[i];

	for (int i=1; i<=n; ++i)
		cin >> b[i];
}

int64_t get(int l, int r) {
	if (l==0)
		return ps[r];
	return ps[r] - ps[l-1];
}

int64_t calc(int64_t x, int l, int r) {
	return p[x] * (x - l + 1) - (ps[x]-ps[l-1]) + ps[r]-ps[x] - p[x] * (r - x);
}

void solve() {
	for (int i=1; i<=n; ++i)
		p[i] = b[i]-a[i];

	sort(p+1, p+n+1);
	// PR(p, n);

	for (int i=1; i<=n; ++i)
		ps[i] = ps[i-1] + p[i];

	int cur = 1;
	int64_t res = INF;

	// debug(calc(3, 1, 5));
	for (int i=1; i+k-1<=n; ++i) {
		while (cur+1<i+k && calc(cur+1, i, i+k-1)<=calc(cur, i, i+k-1))
			++cur;
		res = min(res, calc(cur, i, i+k-1));
	}

	cout << res;
}

int main() {
	#ifdef GLASSES_GIRL
		freopen(FILE_NAME".in", "r", stdin);
		freopen(FILE_NAME".out", "w", stdout);
	#endif
	ios::sync_with_stdio(0); cin.tie(0);

	read_input();
	solve();
}

• 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