Submission #220098

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
220098	2020-04-07 01:14:37	rama_pang	Minerals (JOI19_minerals)	C++14	100 / 100	87 ms	4260 KiB

minerals

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
#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;
int optimal_pivot(int n) {
  static int MAXN = 43005;
  static vector<pair<int, int>> optimal(MAXN, make_pair(1e8, 1e8));
  static bool computed = false;
  if (computed) return optimal[n].second;
  computed = true;
  optimal[0] = optimal[1] = {0, 0};
  for (int i = 2; i < MAXN; i++) {
    int lo = 1, hi = i / 2;
    while (lo < hi) {
      int m1 = (lo + hi) / 2;
      int m2 = m1 + 1;
      int c1 = optimal[m1].first + optimal[i - m1].first + i - 1 + m1;
      int c2 = optimal[m2].first + optimal[i - m2].first + i - 1 + m2;
      if (c1 < c2) {
        hi = m1;
      } else {
        lo = m2;
      }
    }
    optimal[i] = make_pair(optimal[lo].first + optimal[i - lo].first + lo + i - 1, lo);
  }
  return optimal_pivot(n);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 6 / 6
• Subtask 2: 25 / 25
• Subtask 3: 9 / 9
• Subtask 4: 30 / 30
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 10 / 10