oj.uz

Submission #105066

# Submission time Handle Problem Language Result Execution time Memory
105066 2019-04-10T12:30:04 Z polyfish Simfonija (COCI19_simfonija) C++14
110 / 110
 48 ms 4216 KB 
//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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 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 31 ms 2680 KB Output is correct
2 Correct 30 ms 4088 KB Output is correct
3 Correct 33 ms 4216 KB Output is correct

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 2724 KB Output is correct
2 Correct 31 ms 4088 KB Output is correct
3 Correct 33 ms 4088 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 2680 KB Output is correct
2 Correct 36 ms 4116 KB Output is correct
3 Correct 42 ms 4088 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2688 KB Output is correct
2 Correct 35 ms 4168 KB Output is correct
3 Correct 36 ms 4112 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 2680 KB Output is correct
2 Correct 37 ms 4120 KB Output is correct
3 Correct 46 ms 4088 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2680 KB Output is correct
2 Correct 35 ms 2680 KB Output is correct
3 Correct 33 ms 4136 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 2688 KB Output is correct
2 Correct 36 ms 4088 KB Output is correct
3 Correct 35 ms 4216 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 2624 KB Output is correct
2 Correct 39 ms 4088 KB Output is correct
3 Correct 43 ms 4088 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2688 KB Output is correct
2 Correct 31 ms 4088 KB Output is correct
3 Correct 46 ms 4188 KB Output is correct