QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#113873#6632. Minimize MedianITMO_pengzoo#AC ✓1170ms137096kbC++202.4kb2023-06-19 21:42:012023-06-19 21:42:02

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-19 21:42:02]
  • 评测
  • 测评结果:AC
  • 用时:1170ms
  • 内存:137096kb
  • [2023-06-19 21:42:01]
  • 提交

answer

//  Nikita Golikov, 2023

#include <bits/stdc++.h>

using namespace std;

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;

#ifdef GOLIKOV
  #include "/Users/golikovnik/contests/debug.h"
#else
  #define debug(...) ;
#endif

template <class A, class B>
bool smin(A& x, B&& y) {
  if (y < x) {
    x = y;
    return true;
  }
  return false;
}

template <class A, class B>
bool smax(A& x, B&& y) {
  if (x < y) {
    x = y;
    return true;
  }
  return false;
}

void solveTest() {
  int n, m, k;
  cin >> n >> m >> k;
  vector<int> a(n);
  for (auto& x : a) {
    cin >> x;
  }
  vector<ll> cost(m + 2);
  for (int i = 1; i <= m; ++i) {
    cin >> cost[i];
  }
  cost[1] = 0;
  vector<vector<int>> divisors(m + 1);
  for (int i = 1; i <= m; ++i) {
    for (int j = 2 * i; j <= m; j += i) {
      divisors[j].push_back(i);
    }
  }
  for (int i = 1; i <= m; ++i) {
    for (int j : divisors[i]) {
      smin(cost[i], cost[j] + cost[i / j]);
    }
  }
  for (int i = m - 1; i >= 1; --i) {
    smin(cost[i], cost[i + 1]);
  }
  cost[m + 1] = 1e18;
  for (int i = m; i >= 2; --i) {
    smin(cost[m + 1], cost[i] + cost[(m + i) / i]);
  }
  for (int i = m; i >= 1; --i) {
    smin(cost[i], cost[i + 1]);
  }
  debug(cost);

  vector<ll> dp(n);
  auto check = [&](int bound) {
    for (int i = 0; i < n; ++i) {
      int r = max(1, a[i] / (bound + 1) - 3);
      while (a[i] / r > bound) {
        ++r;
      }
      assert(r <= m + 1);
      dp[i] = cost[r];
    }
    debug(bound, dp);
    sort(dp.begin(), dp.end());
    int cnt = 0;
    ll sum = 0;
    while (cnt < n && sum + dp[cnt] <= k) {
      sum += dp[cnt++];
    }
    return cnt >= (n + 1) / 2;
  };

  int left = -1;
  int right = m;
  while (left + 1 != right) {
    int mid = (left + right) / 2;
    (check(mid) ? right : left) = mid;
  }
  cout << right << '\n';
}

int main() {
#ifdef GOLIKOV
  assert(freopen("in", "rt", stdin));
  auto _clock_start = chrono::high_resolution_clock::now();
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int tests_;
  cin >> tests_;
  for (int tt_ = 1; tt_ <= tests_; ++tt_) {
    solveTest();
  }

#ifdef GOLIKOV
  cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
      chrono::high_resolution_clock::now()
          - _clock_start).count() << "ms." << endl;
#endif
  return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3472kb

input:

3
3 5 0
2 5 2
3 2 4 6 13
3 5 3
2 5 3
3 2 4 6 13
3 5 6
2 5 2
3 2 4 6 13

output:

2
2
1

result:

ok 3 number(s): "2 2 1"

Test #2:

score: 0
Accepted
time: 110ms
memory: 3440kb

input:

100000
5 10 5
3 7 1 10 10
11 6 11 6 1 8 9 1 3 1
5 6 51
2 2 2 5 1
42 61 26 59 100 54
5 10 76
7 5 8 4 7
97 4 44 83 61 45 24 88 44 44
5 8 90
1 1 5 1 3
35 15 53 97 71 83 26 7
5 3 52
1 1 3 1 1
22 6 93
5 6 28
6 6 1 3 1
9 31 2 19 10 27
5 8 31
3 6 2 1 2
32 29 13 7 57 34 9 5
5 6 75
3 3 4 5 4
40 56 38 60 17 3...

output:

0
2
0
0
0
0
0
0
3
4
0
0
0
0
1
1
0
0
0
0
1
1
0
2
2
0
0
0
0
0
2
0
0
0
2
2
0
1
0
0
0
0
1
0
2
4
1
1
0
0
2
0
0
7
0
1
0
0
0
1
1
0
1
0
1
0
0
2
1
0
6
3
0
0
1
0
2
0
0
3
0
1
0
1
0
2
0
0
0
0
1
2
1
4
0
0
0
0
0
0
1
2
2
1
2
2
0
1
1
0
0
0
0
0
1
2
1
4
1
0
4
1
2
1
0
0
0
0
1
2
1
0
0
2
3
1
0
1
1
1
0
1
5
0
1
2
0
2
0
0
...

result:

ok 100000 numbers

Test #3:

score: 0
Accepted
time: 61ms
memory: 3504kb

input:

30000
11 7 88
4 6 1 2 1 7 3 3 2 6 3
44 60 14 92 55 88 13
11 11 36
8 9 2 9 1 7 1 7 9 3 8
67 13 49 55 23 18 45 33 8 8 66
11 8 10
3 4 6 3 5 3 1 1 7 5 7
4 14 12 15 21 15 11 7
11 5 65
1 5 3 3 5 1 3 4 5 5 1
27 22 18 56 53
11 8 31
7 6 4 3 1 2 5 1 3 2 7
56 64 56 52 1 10 42 38
11 6 90
6 1 5 3 6 2 2 2 3 1 1
8...

output:

0
1
3
1
0
1
0
1
1
1
1
0
2
1
0
2
2
6
0
0
0
3
1
2
1
1
0
0
2
0
1
6
2
0
0
0
0
2
0
0
0
0
2
1
2
1
0
1
0
0
0
1
1
2
5
1
0
0
7
3
1
3
3
2
0
0
0
3
2
2
0
2
2
3
0
1
0
7
4
0
3
0
1
1
5
0
4
1
4
0
1
2
4
0
2
1
0
1
0
0
4
0
0
2
1
0
0
1
0
1
0
0
0
1
1
0
0
5
2
0
0
0
2
0
0
0
2
0
0
0
0
0
1
1
2
3
1
0
0
0
4
4
0
2
0
3
4
0
1
1
...

result:

ok 30000 numbers

Test #4:

score: 0
Accepted
time: 40ms
memory: 3468kb

input:

10000
21 2 301
2 1 1 2 1 1 1 2 1 2 2 2 2 2 2 2 1 2 1 1 2
91 73
21 16 233
1 6 6 8 10 10 9 3 8 8 8 7 11 6 7 11 9 13 13 11 11
29 88 36 42 98 53 65 44 31 58 27 36 34 51 33 26
21 35 699
11 33 22 24 34 33 24 16 5 12 8 26 34 4 1 33 10 3 9 21 10
56 27 39 44 44 53 75 14 57 20 51 69 85 15 29 50 76 79 37 6 17 ...

output:

1
6
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
3
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
11
0
0
0
0
1
0
0
0
0
3
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
2
0
0
0
0
6
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 10000 numbers

Test #5:

score: 0
Accepted
time: 505ms
memory: 14928kb

input:

10
99999 48959 549895809
17383 33522 48377 31386 19330 13043 27394 37249 36294 12722 8373 37625 12026 13690 14053 30528 16342 31971 17759 23330 19377 6906 2676 9898 35581 3357 38474 28896 7227 46575 20055 8860 38630 48009 37394 20074 31995 24762 36589 33677 5802 16186 22579 2830 43898 14963 41255 30...

output:

0
0
0
0
0
0
0
0
0
0

result:

ok 10 numbers

Test #6:

score: 0
Accepted
time: 601ms
memory: 49004kb

input:

1
999999 293797 278478314
67762 104009 176376 207621 189337 131231 23909 205140 207710 179872 138897 128633 199664 237425 193080 187398 13587 257639 152428 246508 123562 143881 26620 119039 114584 74242 194355 237441 149776 20279 184277 170447 262736 145607 92710 99452 283332 188967 257554 248224 67...

output:

0

result:

ok 1 number(s): "0"

Test #7:

score: 0
Accepted
time: 767ms
memory: 126472kb

input:

1
99999 1000000 709380
3515 30629 61254 18266 46934 53061 981 63751 4639 35121 72295 47911 56251 13323 17732 6035 51729 57468 5653 91728 22114 69445 54695 7726 74817 142 14101 43678 58715 9895 1984 71046 93603 95882 53070 17490 50060 77935 92407 26483 91683 76316 73977 83427 70507 11756 85938 49558 ...

output:

128

result:

ok 1 number(s): "128"

Test #8:

score: 0
Accepted
time: 728ms
memory: 126476kb

input:

1
99999 1000000 730285
4769 751 60305 40567 49044 18757 96490 34566 80175 52321 30028 88070 17465 12640 5851 66927 60188 75361 9700 13297 67790 9112 28913 61594 62427 44745 90109 1018 54884 82000 59979 41302 22946 89424 5747 22952 81452 60845 27911 18257 14441 81453 69309 83941 20741 87909 37929 780...

output:

50000

result:

ok 1 number(s): "50000"

Test #9:

score: 0
Accepted
time: 679ms
memory: 17104kb

input:

10
99959 99959 286229830
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

1
1
1
1
1
1
1
1
1
1

result:

ok 10 numbers

Test #10:

score: 0
Accepted
time: 1170ms
memory: 137016kb

input:

1
999981 999981 329021098
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

1

result:

ok 1 number(s): "1"

Test #11:

score: 0
Accepted
time: 1156ms
memory: 137048kb

input:

1
999975 999975 212118220
23 62 26 86 21 84 44 79 76 82 9 23 45 82 84 51 95 97 32 50 70 34 8 41 48 59 11 25 84 24 80 70 67 67 63 89 39 93 26 63 31 26 26 50 74 1 48 53 27 97 76 16 83 44 40 96 91 97 72 40 85 70 80 65 15 65 81 2 23 46 55 11 52 74 27 84 36 51 49 40 4 45 40 3 81 70 66 31 31 79 64 57 77 1...

output:

98

result:

ok 1 number(s): "98"

Test #12:

score: 0
Accepted
time: 1145ms
memory: 137096kb

input:

1
999999 1000000 2551660
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95...

output:

34484

result:

ok 1 number(s): "34484"

Test #13:

score: 0
Accepted
time: 966ms
memory: 69888kb

input:

2
499999 500000 886493
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 9...

output:

23596
75652

result:

ok 2 number(s): "23596 75652"