oj.uz

Submission #105065

# Submission time Handle Problem Language Result Execution time Memory
105065 2019-04-10T12:28:02 Z polyfish Simfonija (COCI19_simfonija) C++14
0 / 110
 368 ms 3476 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
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 315 ms 3448 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 347 ms 3452 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 321 ms 3452 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 356 ms 3108 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 368 ms 3476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 337 ms 3408 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 351 ms 3456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 326 ms 3436 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 322 ms 3364 KB Output isn't correct
2 Halted 0 ms 0 KB -