oj.uz

Submission #636989

# Submission time Handle Problem Language Result Execution time Memory
636989 2022-08-31T01:23:59 Z iee Simfonija (COCI19_simfonija) C++17
55 / 110
 20 ms 3656 KB 
// iee
#include <bits/stdc++.h>

#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)
#define fi first
#define se second
using ll = long long;
using ull = unsigned long long;
using namespace std;
void work(int);

template <class T> void read(T &x) {
  x = 0;
  int f = 1, ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + (ch - '0');
    ch = getchar();
  }
  x *= f;
}

int main() {
  int TT = 1; // cin >> TT;
  rep(CAS, 1, TT)
    work(CAS);
  return 0;
}
const int N = 1e5 + 5;
int n, k, a[N], b[N], d[N];
ll s[N];
ll calc(int l, int r, int pos) {
  if (pos < l) {
    ll ret = (ll) pos * d[pos] - s[pos];
    ret += (s[l - 1] - s[pos]) - (ll) d[pos] * (l - 1 - pos);
    ret += (s[n] - s[r]) - (ll) d[pos] * (n - r);
    return ret;
  } else {
    pos = r + (pos - (l - 1));
    ll ret = (ll) (l - 1) * d[pos] - s[l - 1];
    ret += (ll) (pos - r) * d[pos] - (s[pos] - s[r]);
    ret += (s[n] - s[pos]) - (ll) (n - pos) * d[pos];
    return ret;
  }
}
void work(int CASE) {
  read(n), read(k);
  int pos = (n - k + 1) / 2;
  rep(i, 1, n) read(a[i]);
  rep(i, 1, n) read(b[i]), d[i] = a[i] - b[i];
  sort(d + 1, d + n + 1);
  rep(i, 1, n) s[i] = s[i - 1] + d[i];
  ll mn = 1e18;
  rep(l, 1, n - k + 1) mn = min(mn, calc(l, l + k - 1, pos));
  printf("%lld", mn);
}

Subtask #1
11.0 / 11.0

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

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2176 KB Output is correct
2 Correct 13 ms 2168 KB Output is correct
3 Correct 11 ms 2132 KB Output is correct

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2192 KB Output is correct
2 Correct 13 ms 2172 KB Output is correct
3 Correct 20 ms 2216 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2164 KB Output is correct
2 Correct 13 ms 2176 KB Output is correct
3 Correct 12 ms 2220 KB Output is correct

Subtask #5
0 / 11.0

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

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2136 KB Output is correct
2 Correct 16 ms 3576 KB Output is correct
3 Incorrect 16 ms 3656 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2260 KB Output is correct
2 Incorrect 13 ms 3544 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

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

Subtask #9
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2252 KB Output is correct
2 Incorrect 16 ms 3572 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2260 KB Output is correct
2 Correct 13 ms 3572 KB Output is correct
3 Correct 19 ms 3580 KB Output is correct