oj.uz

Submission #816230

# Submission time Handle Problem Language Result Execution time Memory
816230 2023-08-09T04:31:23 Z jun6873 Aliens (IOI16_aliens) C++17
100 / 100
 796 ms 165348 KB 
#include <bits/stdc++.h>

#include "aliens.h"
using namespace std;

using lint = long long;
using pint = pair<lint, lint>;
#define x first
#define y second

const lint inf = 1e18;

const int noden = 500004 * 20;
const lint rangel = 0, ranger = 1000000;
struct line {
  line() : a(0), b(inf) {}
  line(lint a, lint b) : a(a), b(b) {}
  lint operator()(lint x) { return a * x + b; }
  lint a, b;
};

struct lichao {
  line f[noden];
  int t[noden], lc[noden], rc[noden], cnt = 1;

  void init() {
    for (int i = 1; i <= cnt; i++) {
      f[i] = line();
      t[i] = lc[i] = rc[i] = 0;
    }
    cnt = 1;
  }

  void update(lint s, lint e, int x, line g, int v) {
    if (g(s) < f[x](s)) swap(f[x], g), swap(t[x], v);
    if (f[x](e) <= g(e)) return;

    lint m = (s + e) / 2;
    if (g(m) < f[x](m)) {
      swap(f[x], g);
      swap(t[x], v);
      if (!lc[x]) lc[x] = ++cnt;
      update(s, m, lc[x], g, v);
    } else {
      if (!rc[x]) rc[x] = ++cnt;
      update(m + 1, e, rc[x], g, v);
    }
  }
  void update(line g, int v) { update(rangel, ranger, 1, g, v); }

  pint query(lint s, lint e, int x, lint p) {
    if (s == e) return pint(f[x](p), t[x]);
    lint m = (s + e) / 2;
    if (p <= m)
      return min(pint(f[x](p), t[x]),
                 lc[x] ? query(s, m, lc[x], p) : pint(inf, 0));
    else
      return min(pint(f[x](p), t[x]),
                 rc[x] ? query(m + 1, e, rc[x], p) : pint(inf, 0));
  }
  pint query(lint p) { return query(rangel, ranger, 1, p); }
} t;

int N, M, K, bef[500004];
lint dp[500004];
vector<pint> p;

lint square(lint x) { return x * x; }
pint opt(lint C) {
  t.init();

  for (int i = 0; i < N; i++) {
    t.update(line(-4 * (p[i].x - 1),
                  2 * square(p[i].x - 1) + (i == 0 ? 0 : dp[i - 1])),
             i - 1);

    tie(dp[i], bef[i]) = t.query(p[i].y);
    dp[i] += 2 * square(p[i].y) + C;
    if (i + 1 < N and p[i + 1].x <= p[i].y) {
      dp[i] -= 2 * square(p[i].y - p[i + 1].x + 1);
    }
  }

  int cnt = 0;
  for (int i = N - 1; i >= 0; i = bef[i]) cnt++;

  return pint(dp[N - 1], cnt);
}

long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
  N = n;
  M = m;
  K = k;
  for (int i = 0; i < N; i++) p.emplace_back(min(r[i], c[i]), max(r[i], c[i]));

  sort(p.begin(), p.end(),
       [](pint x, pint y) { return x.x < y.x or (x.x == y.x and x.y > y.y); });

  vector<pint> realp;
  for (int i = 0, ymx = -1; i < N; i++)
    if (ymx < p[i].y) {
      realp.push_back(p[i]);
      ymx = p[i].y;
    }

  swap(p, realp);
  N = p.size();

  lint s = -1, e = 2e12 + 7;

  while (s + 1 < e) {
    lint m = (s + e) / 2;
    if (opt(m).y <= K)
      e = m;
    else
      s = m;
  }

  pint ans = opt(e);

  return (ans.x - K * e) / 2;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 156880 KB Correct answer: answer = 4
2 Correct 73 ms 156864 KB Correct answer: answer = 4
3 Correct 57 ms 156768 KB Correct answer: answer = 4
4 Correct 67 ms 156856 KB Correct answer: answer = 12
5 Correct 69 ms 156844 KB Correct answer: answer = 52
6 Correct 60 ms 156764 KB Correct answer: answer = 210
7 Correct 57 ms 156832 KB Correct answer: answer = 88
8 Correct 57 ms 156844 KB Correct answer: answer = 7696
9 Correct 65 ms 156788 KB Correct answer: answer = 1
10 Correct 63 ms 156852 KB Correct answer: answer = 2374
11 Correct 57 ms 156860 KB Correct answer: answer = 9502
12 Correct 57 ms 156872 KB Correct answer: answer = 49
13 Correct 72 ms 156872 KB Correct answer: answer = 151
14 Correct 61 ms 156856 KB Correct answer: answer = 7550
15 Correct 57 ms 156876 KB Correct answer: answer = 7220
16 Correct 58 ms 156820 KB Correct answer: answer = 7550
17 Correct 65 ms 156880 KB Correct answer: answer = 10000
18 Correct 56 ms 156856 KB Correct answer: answer = 10000
19 Correct 57 ms 156860 KB Correct answer: answer = 624
20 Correct 59 ms 156876 KB Correct answer: answer = 10000

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 156872 KB Correct answer: answer = 1
2 Correct 62 ms 156844 KB Correct answer: answer = 4
3 Correct 75 ms 156812 KB Correct answer: answer = 1
4 Correct 72 ms 156836 KB Correct answer: answer = 5
5 Correct 60 ms 156808 KB Correct answer: answer = 41
6 Correct 64 ms 156788 KB Correct answer: answer = 71923
7 Correct 62 ms 156932 KB Correct answer: answer = 77137
8 Correct 63 ms 156844 KB Correct answer: answer = 764
9 Correct 63 ms 156844 KB Correct answer: answer = 250000
10 Correct 62 ms 156908 KB Correct answer: answer = 500
11 Correct 67 ms 156876 KB Correct answer: answer = 32
12 Correct 78 ms 156896 KB Correct answer: answer = 130050
13 Correct 62 ms 156876 KB Correct answer: answer = 5110
14 Correct 61 ms 156896 KB Correct answer: answer = 2626
15 Correct 65 ms 156816 KB Correct answer: answer = 796
16 Correct 67 ms 156920 KB Correct answer: answer = 7580
17 Correct 64 ms 156900 KB Correct answer: answer = 1904
18 Correct 62 ms 156860 KB Correct answer: answer = 996004
19 Correct 61 ms 156852 KB Correct answer: answer = 38817
20 Correct 61 ms 156868 KB Correct answer: answer = 4096
21 Correct 59 ms 156808 KB Correct answer: answer = 1
22 Correct 67 ms 156784 KB Correct answer: answer = 1
23 Correct 76 ms 156868 KB Correct answer: answer = 2040
24 Correct 76 ms 156896 KB Correct answer: answer = 2

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 156880 KB Correct answer: answer = 4
2 Correct 73 ms 156864 KB Correct answer: answer = 4
3 Correct 57 ms 156768 KB Correct answer: answer = 4
4 Correct 67 ms 156856 KB Correct answer: answer = 12
5 Correct 69 ms 156844 KB Correct answer: answer = 52
6 Correct 60 ms 156764 KB Correct answer: answer = 210
7 Correct 57 ms 156832 KB Correct answer: answer = 88
8 Correct 57 ms 156844 KB Correct answer: answer = 7696
9 Correct 65 ms 156788 KB Correct answer: answer = 1
10 Correct 63 ms 156852 KB Correct answer: answer = 2374
11 Correct 57 ms 156860 KB Correct answer: answer = 9502
12 Correct 57 ms 156872 KB Correct answer: answer = 49
13 Correct 72 ms 156872 KB Correct answer: answer = 151
14 Correct 61 ms 156856 KB Correct answer: answer = 7550
15 Correct 57 ms 156876 KB Correct answer: answer = 7220
16 Correct 58 ms 156820 KB Correct answer: answer = 7550
17 Correct 65 ms 156880 KB Correct answer: answer = 10000
18 Correct 56 ms 156856 KB Correct answer: answer = 10000
19 Correct 57 ms 156860 KB Correct answer: answer = 624
20 Correct 59 ms 156876 KB Correct answer: answer = 10000
21 Correct 63 ms 156872 KB Correct answer: answer = 1
22 Correct 62 ms 156844 KB Correct answer: answer = 4
23 Correct 75 ms 156812 KB Correct answer: answer = 1
24 Correct 72 ms 156836 KB Correct answer: answer = 5
25 Correct 60 ms 156808 KB Correct answer: answer = 41
26 Correct 64 ms 156788 KB Correct answer: answer = 71923
27 Correct 62 ms 156932 KB Correct answer: answer = 77137
28 Correct 63 ms 156844 KB Correct answer: answer = 764
29 Correct 63 ms 156844 KB Correct answer: answer = 250000
30 Correct 62 ms 156908 KB Correct answer: answer = 500
31 Correct 67 ms 156876 KB Correct answer: answer = 32
32 Correct 78 ms 156896 KB Correct answer: answer = 130050
33 Correct 62 ms 156876 KB Correct answer: answer = 5110
34 Correct 61 ms 156896 KB Correct answer: answer = 2626
35 Correct 65 ms 156816 KB Correct answer: answer = 796
36 Correct 67 ms 156920 KB Correct answer: answer = 7580
37 Correct 64 ms 156900 KB Correct answer: answer = 1904
38 Correct 62 ms 156860 KB Correct answer: answer = 996004
39 Correct 61 ms 156852 KB Correct answer: answer = 38817
40 Correct 61 ms 156868 KB Correct answer: answer = 4096
41 Correct 59 ms 156808 KB Correct answer: answer = 1
42 Correct 67 ms 156784 KB Correct answer: answer = 1
43 Correct 76 ms 156868 KB Correct answer: answer = 2040
44 Correct 76 ms 156896 KB Correct answer: answer = 2
45 Correct 67 ms 156824 KB Correct answer: answer = 4
46 Correct 59 ms 156772 KB Correct answer: answer = 9
47 Correct 62 ms 156772 KB Correct answer: answer = 9
48 Correct 60 ms 156868 KB Correct answer: answer = 21
49 Correct 67 ms 156788 KB Correct answer: answer = 71
50 Correct 62 ms 156856 KB Correct answer: answer = 77
51 Correct 62 ms 156812 KB Correct answer: answer = 400
52 Correct 62 ms 156864 KB Correct answer: answer = 996004
53 Correct 61 ms 156844 KB Correct answer: answer = 997310
54 Correct 60 ms 156876 KB Correct answer: answer = 990781
55 Correct 60 ms 156888 KB Correct answer: answer = 996545
56 Correct 87 ms 156908 KB Correct answer: answer = 484
57 Correct 61 ms 156780 KB Correct answer: answer = 484
58 Correct 62 ms 156820 KB Correct answer: answer = 63501
59 Correct 63 ms 156868 KB Correct answer: answer = 323501
60 Correct 73 ms 156836 KB Correct answer: answer = 752500
61 Correct 72 ms 156892 KB Correct answer: answer = 761480
62 Correct 62 ms 156792 KB Correct answer: answer = 758932
63 Correct 63 ms 156796 KB Correct answer: answer = 1000000
64 Correct 64 ms 156920 KB Correct answer: answer = 750500
65 Correct 61 ms 156876 KB Correct answer: answer = 1000000
66 Correct 60 ms 156788 KB Correct answer: answer = 250000
67 Correct 67 ms 156864 KB Correct answer: answer = 250000
68 Correct 67 ms 156888 KB Correct answer: answer = 1000000
69 Correct 62 ms 156808 KB Correct answer: answer = 994009
70 Correct 71 ms 156876 KB Correct answer: answer = 59315
71 Correct 62 ms 156808 KB Correct answer: answer = 25454
72 Correct 85 ms 156900 KB Correct answer: answer = 1504
73 Correct 63 ms 156800 KB Correct answer: answer = 37486
74 Correct 63 ms 156860 KB Correct answer: answer = 4284
75 Correct 68 ms 156880 KB Correct answer: answer = 158008
76 Correct 64 ms 156876 KB Correct answer: answer = 51860
77 Correct 60 ms 156896 KB Correct answer: answer = 12985

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 156880 KB Correct answer: answer = 4
2 Correct 73 ms 156864 KB Correct answer: answer = 4
3 Correct 57 ms 156768 KB Correct answer: answer = 4
4 Correct 67 ms 156856 KB Correct answer: answer = 12
5 Correct 69 ms 156844 KB Correct answer: answer = 52
6 Correct 60 ms 156764 KB Correct answer: answer = 210
7 Correct 57 ms 156832 KB Correct answer: answer = 88
8 Correct 57 ms 156844 KB Correct answer: answer = 7696
9 Correct 65 ms 156788 KB Correct answer: answer = 1
10 Correct 63 ms 156852 KB Correct answer: answer = 2374
11 Correct 57 ms 156860 KB Correct answer: answer = 9502
12 Correct 57 ms 156872 KB Correct answer: answer = 49
13 Correct 72 ms 156872 KB Correct answer: answer = 151
14 Correct 61 ms 156856 KB Correct answer: answer = 7550
15 Correct 57 ms 156876 KB Correct answer: answer = 7220
16 Correct 58 ms 156820 KB Correct answer: answer = 7550
17 Correct 65 ms 156880 KB Correct answer: answer = 10000
18 Correct 56 ms 156856 KB Correct answer: answer = 10000
19 Correct 57 ms 156860 KB Correct answer: answer = 624
20 Correct 59 ms 156876 KB Correct answer: answer = 10000
21 Correct 63 ms 156872 KB Correct answer: answer = 1
22 Correct 62 ms 156844 KB Correct answer: answer = 4
23 Correct 75 ms 156812 KB Correct answer: answer = 1
24 Correct 72 ms 156836 KB Correct answer: answer = 5
25 Correct 60 ms 156808 KB Correct answer: answer = 41
26 Correct 64 ms 156788 KB Correct answer: answer = 71923
27 Correct 62 ms 156932 KB Correct answer: answer = 77137
28 Correct 63 ms 156844 KB Correct answer: answer = 764
29 Correct 63 ms 156844 KB Correct answer: answer = 250000
30 Correct 62 ms 156908 KB Correct answer: answer = 500
31 Correct 67 ms 156876 KB Correct answer: answer = 32
32 Correct 78 ms 156896 KB Correct answer: answer = 130050
33 Correct 62 ms 156876 KB Correct answer: answer = 5110
34 Correct 61 ms 156896 KB Correct answer: answer = 2626
35 Correct 65 ms 156816 KB Correct answer: answer = 796
36 Correct 67 ms 156920 KB Correct answer: answer = 7580
37 Correct 64 ms 156900 KB Correct answer: answer = 1904
38 Correct 62 ms 156860 KB Correct answer: answer = 996004
39 Correct 61 ms 156852 KB Correct answer: answer = 38817
40 Correct 61 ms 156868 KB Correct answer: answer = 4096
41 Correct 59 ms 156808 KB Correct answer: answer = 1
42 Correct 67 ms 156784 KB Correct answer: answer = 1
43 Correct 76 ms 156868 KB Correct answer: answer = 2040
44 Correct 76 ms 156896 KB Correct answer: answer = 2
45 Correct 67 ms 156824 KB Correct answer: answer = 4
46 Correct 59 ms 156772 KB Correct answer: answer = 9
47 Correct 62 ms 156772 KB Correct answer: answer = 9
48 Correct 60 ms 156868 KB Correct answer: answer = 21
49 Correct 67 ms 156788 KB Correct answer: answer = 71
50 Correct 62 ms 156856 KB Correct answer: answer = 77
51 Correct 62 ms 156812 KB Correct answer: answer = 400
52 Correct 62 ms 156864 KB Correct answer: answer = 996004
53 Correct 61 ms 156844 KB Correct answer: answer = 997310
54 Correct 60 ms 156876 KB Correct answer: answer = 990781
55 Correct 60 ms 156888 KB Correct answer: answer = 996545
56 Correct 87 ms 156908 KB Correct answer: answer = 484
57 Correct 61 ms 156780 KB Correct answer: answer = 484
58 Correct 62 ms 156820 KB Correct answer: answer = 63501
59 Correct 63 ms 156868 KB Correct answer: answer = 323501
60 Correct 73 ms 156836 KB Correct answer: answer = 752500
61 Correct 72 ms 156892 KB Correct answer: answer = 761480
62 Correct 62 ms 156792 KB Correct answer: answer = 758932
63 Correct 63 ms 156796 KB Correct answer: answer = 1000000
64 Correct 64 ms 156920 KB Correct answer: answer = 750500
65 Correct 61 ms 156876 KB Correct answer: answer = 1000000
66 Correct 60 ms 156788 KB Correct answer: answer = 250000
67 Correct 67 ms 156864 KB Correct answer: answer = 250000
68 Correct 67 ms 156888 KB Correct answer: answer = 1000000
69 Correct 62 ms 156808 KB Correct answer: answer = 994009
70 Correct 71 ms 156876 KB Correct answer: answer = 59315
71 Correct 62 ms 156808 KB Correct answer: answer = 25454
72 Correct 85 ms 156900 KB Correct answer: answer = 1504
73 Correct 63 ms 156800 KB Correct answer: answer = 37486
74 Correct 63 ms 156860 KB Correct answer: answer = 4284
75 Correct 68 ms 156880 KB Correct answer: answer = 158008
76 Correct 64 ms 156876 KB Correct answer: answer = 51860
77 Correct 60 ms 156896 KB Correct answer: answer = 12985
78 Correct 65 ms 157124 KB Correct answer: answer = 997864126212
79 Correct 79 ms 157036 KB Correct answer: answer = 998608411647
80 Correct 60 ms 157000 KB Correct answer: answer = 995265560477
81 Correct 81 ms 157172 KB Correct answer: answer = 10125000
82 Correct 78 ms 157232 KB Correct answer: answer = 2291668
83 Correct 72 ms 157000 KB Correct answer: answer = 42388
84 Correct 76 ms 157004 KB Correct answer: answer = 10318
85 Correct 76 ms 156952 KB Correct answer: answer = 3416
86 Correct 69 ms 157164 KB Correct answer: answer = 331708193881
87 Correct 80 ms 157432 KB Correct answer: answer = 2861193756
88 Correct 79 ms 157264 KB Correct answer: answer = 114646930
89 Correct 81 ms 157260 KB Correct answer: answer = 9280921
90 Correct 80 ms 157200 KB Correct answer: answer = 999984053400
91 Correct 92 ms 157204 KB Correct answer: answer = 750935949134
92 Correct 68 ms 157152 KB Correct answer: answer = 1000000000000
93 Correct 63 ms 157004 KB Correct answer: answer = 998762383161
94 Correct 73 ms 157216 KB Correct answer: answer = 23017412908
95 Correct 67 ms 157068 KB Correct answer: answer = 728143410622
96 Correct 63 ms 157004 KB Correct answer: answer = 2
97 Correct 81 ms 157256 KB Correct answer: answer = 1824916
98 Correct 80 ms 157224 KB Correct answer: answer = 10680029
99 Correct 85 ms 157404 KB Correct answer: answer = 18351700
100 Correct 72 ms 157132 KB Correct answer: answer = 16040026
101 Correct 65 ms 157052 KB Correct answer: answer = 253968628325
102 Correct 72 ms 157016 KB Correct answer: answer = 10267
103 Correct 83 ms 157184 KB Correct answer: answer = 2582408
104 Correct 62 ms 157132 KB Correct answer: answer = 78024964781
105 Correct 65 ms 157236 KB Correct answer: answer = 9866346457
106 Correct 65 ms 157076 KB Correct answer: answer = 3327720949
107 Correct 63 ms 157100 KB Correct answer: answer = 86064128360
108 Correct 70 ms 157060 KB Correct answer: answer = 12698259150
109 Correct 74 ms 157160 KB Correct answer: answer = 1185259288

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 156880 KB Correct answer: answer = 4
2 Correct 73 ms 156864 KB Correct answer: answer = 4
3 Correct 57 ms 156768 KB Correct answer: answer = 4
4 Correct 67 ms 156856 KB Correct answer: answer = 12
5 Correct 69 ms 156844 KB Correct answer: answer = 52
6 Correct 60 ms 156764 KB Correct answer: answer = 210
7 Correct 57 ms 156832 KB Correct answer: answer = 88
8 Correct 57 ms 156844 KB Correct answer: answer = 7696
9 Correct 65 ms 156788 KB Correct answer: answer = 1
10 Correct 63 ms 156852 KB Correct answer: answer = 2374
11 Correct 57 ms 156860 KB Correct answer: answer = 9502
12 Correct 57 ms 156872 KB Correct answer: answer = 49
13 Correct 72 ms 156872 KB Correct answer: answer = 151
14 Correct 61 ms 156856 KB Correct answer: answer = 7550
15 Correct 57 ms 156876 KB Correct answer: answer = 7220
16 Correct 58 ms 156820 KB Correct answer: answer = 7550
17 Correct 65 ms 156880 KB Correct answer: answer = 10000
18 Correct 56 ms 156856 KB Correct answer: answer = 10000
19 Correct 57 ms 156860 KB Correct answer: answer = 624
20 Correct 59 ms 156876 KB Correct answer: answer = 10000
21 Correct 63 ms 156872 KB Correct answer: answer = 1
22 Correct 62 ms 156844 KB Correct answer: answer = 4
23 Correct 75 ms 156812 KB Correct answer: answer = 1
24 Correct 72 ms 156836 KB Correct answer: answer = 5
25 Correct 60 ms 156808 KB Correct answer: answer = 41
26 Correct 64 ms 156788 KB Correct answer: answer = 71923
27 Correct 62 ms 156932 KB Correct answer: answer = 77137
28 Correct 63 ms 156844 KB Correct answer: answer = 764
29 Correct 63 ms 156844 KB Correct answer: answer = 250000
30 Correct 62 ms 156908 KB Correct answer: answer = 500
31 Correct 67 ms 156876 KB Correct answer: answer = 32
32 Correct 78 ms 156896 KB Correct answer: answer = 130050
33 Correct 62 ms 156876 KB Correct answer: answer = 5110
34 Correct 61 ms 156896 KB Correct answer: answer = 2626
35 Correct 65 ms 156816 KB Correct answer: answer = 796
36 Correct 67 ms 156920 KB Correct answer: answer = 7580
37 Correct 64 ms 156900 KB Correct answer: answer = 1904
38 Correct 62 ms 156860 KB Correct answer: answer = 996004
39 Correct 61 ms 156852 KB Correct answer: answer = 38817
40 Correct 61 ms 156868 KB Correct answer: answer = 4096
41 Correct 59 ms 156808 KB Correct answer: answer = 1
42 Correct 67 ms 156784 KB Correct answer: answer = 1
43 Correct 76 ms 156868 KB Correct answer: answer = 2040
44 Correct 76 ms 156896 KB Correct answer: answer = 2
45 Correct 67 ms 156824 KB Correct answer: answer = 4
46 Correct 59 ms 156772 KB Correct answer: answer = 9
47 Correct 62 ms 156772 KB Correct answer: answer = 9
48 Correct 60 ms 156868 KB Correct answer: answer = 21
49 Correct 67 ms 156788 KB Correct answer: answer = 71
50 Correct 62 ms 156856 KB Correct answer: answer = 77
51 Correct 62 ms 156812 KB Correct answer: answer = 400
52 Correct 62 ms 156864 KB Correct answer: answer = 996004
53 Correct 61 ms 156844 KB Correct answer: answer = 997310
54 Correct 60 ms 156876 KB Correct answer: answer = 990781
55 Correct 60 ms 156888 KB Correct answer: answer = 996545
56 Correct 87 ms 156908 KB Correct answer: answer = 484
57 Correct 61 ms 156780 KB Correct answer: answer = 484
58 Correct 62 ms 156820 KB Correct answer: answer = 63501
59 Correct 63 ms 156868 KB Correct answer: answer = 323501
60 Correct 73 ms 156836 KB Correct answer: answer = 752500
61 Correct 72 ms 156892 KB Correct answer: answer = 761480
62 Correct 62 ms 156792 KB Correct answer: answer = 758932
63 Correct 63 ms 156796 KB Correct answer: answer = 1000000
64 Correct 64 ms 156920 KB Correct answer: answer = 750500
65 Correct 61 ms 156876 KB Correct answer: answer = 1000000
66 Correct 60 ms 156788 KB Correct answer: answer = 250000
67 Correct 67 ms 156864 KB Correct answer: answer = 250000
68 Correct 67 ms 156888 KB Correct answer: answer = 1000000
69 Correct 62 ms 156808 KB Correct answer: answer = 994009
70 Correct 71 ms 156876 KB Correct answer: answer = 59315
71 Correct 62 ms 156808 KB Correct answer: answer = 25454
72 Correct 85 ms 156900 KB Correct answer: answer = 1504
73 Correct 63 ms 156800 KB Correct answer: answer = 37486
74 Correct 63 ms 156860 KB Correct answer: answer = 4284
75 Correct 68 ms 156880 KB Correct answer: answer = 158008
76 Correct 64 ms 156876 KB Correct answer: answer = 51860
77 Correct 60 ms 156896 KB Correct answer: answer = 12985
78 Correct 65 ms 157124 KB Correct answer: answer = 997864126212
79 Correct 79 ms 157036 KB Correct answer: answer = 998608411647
80 Correct 60 ms 157000 KB Correct answer: answer = 995265560477
81 Correct 81 ms 157172 KB Correct answer: answer = 10125000
82 Correct 78 ms 157232 KB Correct answer: answer = 2291668
83 Correct 72 ms 157000 KB Correct answer: answer = 42388
84 Correct 76 ms 157004 KB Correct answer: answer = 10318
85 Correct 76 ms 156952 KB Correct answer: answer = 3416
86 Correct 69 ms 157164 KB Correct answer: answer = 331708193881
87 Correct 80 ms 157432 KB Correct answer: answer = 2861193756
88 Correct 79 ms 157264 KB Correct answer: answer = 114646930
89 Correct 81 ms 157260 KB Correct answer: answer = 9280921
90 Correct 80 ms 157200 KB Correct answer: answer = 999984053400
91 Correct 92 ms 157204 KB Correct answer: answer = 750935949134
92 Correct 68 ms 157152 KB Correct answer: answer = 1000000000000
93 Correct 63 ms 157004 KB Correct answer: answer = 998762383161
94 Correct 73 ms 157216 KB Correct answer: answer = 23017412908
95 Correct 67 ms 157068 KB Correct answer: answer = 728143410622
96 Correct 63 ms 157004 KB Correct answer: answer = 2
97 Correct 81 ms 157256 KB Correct answer: answer = 1824916
98 Correct 80 ms 157224 KB Correct answer: answer = 10680029
99 Correct 85 ms 157404 KB Correct answer: answer = 18351700
100 Correct 72 ms 157132 KB Correct answer: answer = 16040026
101 Correct 65 ms 157052 KB Correct answer: answer = 253968628325
102 Correct 72 ms 157016 KB Correct answer: answer = 10267
103 Correct 83 ms 157184 KB Correct answer: answer = 2582408
104 Correct 62 ms 157132 KB Correct answer: answer = 78024964781
105 Correct 65 ms 157236 KB Correct answer: answer = 9866346457
106 Correct 65 ms 157076 KB Correct answer: answer = 3327720949
107 Correct 63 ms 157100 KB Correct answer: answer = 86064128360
108 Correct 70 ms 157060 KB Correct answer: answer = 12698259150
109 Correct 74 ms 157160 KB Correct answer: answer = 1185259288
110 Correct 80 ms 159376 KB Correct answer: answer = 999889968863
111 Correct 69 ms 159444 KB Correct answer: answer = 999861384931
112 Correct 76 ms 159476 KB Correct answer: answer = 999811809929
113 Correct 74 ms 159428 KB Correct answer: answer = 999869756441
114 Correct 241 ms 160744 KB Correct answer: answer = 1700000000
115 Correct 363 ms 161036 KB Correct answer: answer = 131666670
116 Correct 139 ms 158296 KB Correct answer: answer = 89478486
117 Correct 156 ms 158340 KB Correct answer: answer = 4971040
118 Correct 154 ms 158312 KB Correct answer: answer = 2711494
119 Correct 381 ms 161100 KB Correct answer: answer = 25252530
120 Correct 363 ms 161084 KB Correct answer: answer = 62500000
121 Correct 157 ms 160652 KB Correct answer: answer = 333175097780
122 Correct 215 ms 160656 KB Correct answer: answer = 33121180179
123 Correct 228 ms 160664 KB Correct answer: answer = 9802314015
124 Correct 368 ms 161080 KB Correct answer: answer = 32567551
125 Correct 403 ms 161044 KB Correct answer: answer = 997525000000
126 Correct 232 ms 160648 KB Correct answer: answer = 752723538884
127 Correct 70 ms 159400 KB Correct answer: answer = 1000000000000
128 Correct 73 ms 159472 KB Correct answer: answer = 999978000121
129 Correct 75 ms 159488 KB Correct answer: answer = 745986144735
130 Correct 68 ms 158992 KB Correct answer: answer = 2
131 Correct 363 ms 161144 KB Correct answer: answer = 277966670
132 Correct 259 ms 160944 KB Correct answer: answer = 2500900082
133 Correct 94 ms 159408 KB Correct answer: answer = 301248349636
134 Correct 207 ms 158920 KB Correct answer: answer = 14118891
135 Correct 79 ms 159392 KB Correct answer: answer = 14384977265
136 Correct 74 ms 159356 KB Correct answer: answer = 3681368330
137 Correct 86 ms 159380 KB Correct answer: answer = 2720316816

Subtask #6
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 156880 KB Correct answer: answer = 4
2 Correct 73 ms 156864 KB Correct answer: answer = 4
3 Correct 57 ms 156768 KB Correct answer: answer = 4
4 Correct 67 ms 156856 KB Correct answer: answer = 12
5 Correct 69 ms 156844 KB Correct answer: answer = 52
6 Correct 60 ms 156764 KB Correct answer: answer = 210
7 Correct 57 ms 156832 KB Correct answer: answer = 88
8 Correct 57 ms 156844 KB Correct answer: answer = 7696
9 Correct 65 ms 156788 KB Correct answer: answer = 1
10 Correct 63 ms 156852 KB Correct answer: answer = 2374
11 Correct 57 ms 156860 KB Correct answer: answer = 9502
12 Correct 57 ms 156872 KB Correct answer: answer = 49
13 Correct 72 ms 156872 KB Correct answer: answer = 151
14 Correct 61 ms 156856 KB Correct answer: answer = 7550
15 Correct 57 ms 156876 KB Correct answer: answer = 7220
16 Correct 58 ms 156820 KB Correct answer: answer = 7550
17 Correct 65 ms 156880 KB Correct answer: answer = 10000
18 Correct 56 ms 156856 KB Correct answer: answer = 10000
19 Correct 57 ms 156860 KB Correct answer: answer = 624
20 Correct 59 ms 156876 KB Correct answer: answer = 10000
21 Correct 63 ms 156872 KB Correct answer: answer = 1
22 Correct 62 ms 156844 KB Correct answer: answer = 4
23 Correct 75 ms 156812 KB Correct answer: answer = 1
24 Correct 72 ms 156836 KB Correct answer: answer = 5
25 Correct 60 ms 156808 KB Correct answer: answer = 41
26 Correct 64 ms 156788 KB Correct answer: answer = 71923
27 Correct 62 ms 156932 KB Correct answer: answer = 77137
28 Correct 63 ms 156844 KB Correct answer: answer = 764
29 Correct 63 ms 156844 KB Correct answer: answer = 250000
30 Correct 62 ms 156908 KB Correct answer: answer = 500
31 Correct 67 ms 156876 KB Correct answer: answer = 32
32 Correct 78 ms 156896 KB Correct answer: answer = 130050
33 Correct 62 ms 156876 KB Correct answer: answer = 5110
34 Correct 61 ms 156896 KB Correct answer: answer = 2626
35 Correct 65 ms 156816 KB Correct answer: answer = 796
36 Correct 67 ms 156920 KB Correct answer: answer = 7580
37 Correct 64 ms 156900 KB Correct answer: answer = 1904
38 Correct 62 ms 156860 KB Correct answer: answer = 996004
39 Correct 61 ms 156852 KB Correct answer: answer = 38817
40 Correct 61 ms 156868 KB Correct answer: answer = 4096
41 Correct 59 ms 156808 KB Correct answer: answer = 1
42 Correct 67 ms 156784 KB Correct answer: answer = 1
43 Correct 76 ms 156868 KB Correct answer: answer = 2040
44 Correct 76 ms 156896 KB Correct answer: answer = 2
45 Correct 67 ms 156824 KB Correct answer: answer = 4
46 Correct 59 ms 156772 KB Correct answer: answer = 9
47 Correct 62 ms 156772 KB Correct answer: answer = 9
48 Correct 60 ms 156868 KB Correct answer: answer = 21
49 Correct 67 ms 156788 KB Correct answer: answer = 71
50 Correct 62 ms 156856 KB Correct answer: answer = 77
51 Correct 62 ms 156812 KB Correct answer: answer = 400
52 Correct 62 ms 156864 KB Correct answer: answer = 996004
53 Correct 61 ms 156844 KB Correct answer: answer = 997310
54 Correct 60 ms 156876 KB Correct answer: answer = 990781
55 Correct 60 ms 156888 KB Correct answer: answer = 996545
56 Correct 87 ms 156908 KB Correct answer: answer = 484
57 Correct 61 ms 156780 KB Correct answer: answer = 484
58 Correct 62 ms 156820 KB Correct answer: answer = 63501
59 Correct 63 ms 156868 KB Correct answer: answer = 323501
60 Correct 73 ms 156836 KB Correct answer: answer = 752500
61 Correct 72 ms 156892 KB Correct answer: answer = 761480
62 Correct 62 ms 156792 KB Correct answer: answer = 758932
63 Correct 63 ms 156796 KB Correct answer: answer = 1000000
64 Correct 64 ms 156920 KB Correct answer: answer = 750500
65 Correct 61 ms 156876 KB Correct answer: answer = 1000000
66 Correct 60 ms 156788 KB Correct answer: answer = 250000
67 Correct 67 ms 156864 KB Correct answer: answer = 250000
68 Correct 67 ms 156888 KB Correct answer: answer = 1000000
69 Correct 62 ms 156808 KB Correct answer: answer = 994009
70 Correct 71 ms 156876 KB Correct answer: answer = 59315
71 Correct 62 ms 156808 KB Correct answer: answer = 25454
72 Correct 85 ms 156900 KB Correct answer: answer = 1504
73 Correct 63 ms 156800 KB Correct answer: answer = 37486
74 Correct 63 ms 156860 KB Correct answer: answer = 4284
75 Correct 68 ms 156880 KB Correct answer: answer = 158008
76 Correct 64 ms 156876 KB Correct answer: answer = 51860
77 Correct 60 ms 156896 KB Correct answer: answer = 12985
78 Correct 65 ms 157124 KB Correct answer: answer = 997864126212
79 Correct 79 ms 157036 KB Correct answer: answer = 998608411647
80 Correct 60 ms 157000 KB Correct answer: answer = 995265560477
81 Correct 81 ms 157172 KB Correct answer: answer = 10125000
82 Correct 78 ms 157232 KB Correct answer: answer = 2291668
83 Correct 72 ms 157000 KB Correct answer: answer = 42388
84 Correct 76 ms 157004 KB Correct answer: answer = 10318
85 Correct 76 ms 156952 KB Correct answer: answer = 3416
86 Correct 69 ms 157164 KB Correct answer: answer = 331708193881
87 Correct 80 ms 157432 KB Correct answer: answer = 2861193756
88 Correct 79 ms 157264 KB Correct answer: answer = 114646930
89 Correct 81 ms 157260 KB Correct answer: answer = 9280921
90 Correct 80 ms 157200 KB Correct answer: answer = 999984053400
91 Correct 92 ms 157204 KB Correct answer: answer = 750935949134
92 Correct 68 ms 157152 KB Correct answer: answer = 1000000000000
93 Correct 63 ms 157004 KB Correct answer: answer = 998762383161
94 Correct 73 ms 157216 KB Correct answer: answer = 23017412908
95 Correct 67 ms 157068 KB Correct answer: answer = 728143410622
96 Correct 63 ms 157004 KB Correct answer: answer = 2
97 Correct 81 ms 157256 KB Correct answer: answer = 1824916
98 Correct 80 ms 157224 KB Correct answer: answer = 10680029
99 Correct 85 ms 157404 KB Correct answer: answer = 18351700
100 Correct 72 ms 157132 KB Correct answer: answer = 16040026
101 Correct 65 ms 157052 KB Correct answer: answer = 253968628325
102 Correct 72 ms 157016 KB Correct answer: answer = 10267
103 Correct 83 ms 157184 KB Correct answer: answer = 2582408
104 Correct 62 ms 157132 KB Correct answer: answer = 78024964781
105 Correct 65 ms 157236 KB Correct answer: answer = 9866346457
106 Correct 65 ms 157076 KB Correct answer: answer = 3327720949
107 Correct 63 ms 157100 KB Correct answer: answer = 86064128360
108 Correct 70 ms 157060 KB Correct answer: answer = 12698259150
109 Correct 74 ms 157160 KB Correct answer: answer = 1185259288
110 Correct 80 ms 159376 KB Correct answer: answer = 999889968863
111 Correct 69 ms 159444 KB Correct answer: answer = 999861384931
112 Correct 76 ms 159476 KB Correct answer: answer = 999811809929
113 Correct 74 ms 159428 KB Correct answer: answer = 999869756441
114 Correct 241 ms 160744 KB Correct answer: answer = 1700000000
115 Correct 363 ms 161036 KB Correct answer: answer = 131666670
116 Correct 139 ms 158296 KB Correct answer: answer = 89478486
117 Correct 156 ms 158340 KB Correct answer: answer = 4971040
118 Correct 154 ms 158312 KB Correct answer: answer = 2711494
119 Correct 381 ms 161100 KB Correct answer: answer = 25252530
120 Correct 363 ms 161084 KB Correct answer: answer = 62500000
121 Correct 157 ms 160652 KB Correct answer: answer = 333175097780
122 Correct 215 ms 160656 KB Correct answer: answer = 33121180179
123 Correct 228 ms 160664 KB Correct answer: answer = 9802314015
124 Correct 368 ms 161080 KB Correct answer: answer = 32567551
125 Correct 403 ms 161044 KB Correct answer: answer = 997525000000
126 Correct 232 ms 160648 KB Correct answer: answer = 752723538884
127 Correct 70 ms 159400 KB Correct answer: answer = 1000000000000
128 Correct 73 ms 159472 KB Correct answer: answer = 999978000121
129 Correct 75 ms 159488 KB Correct answer: answer = 745986144735
130 Correct 68 ms 158992 KB Correct answer: answer = 2
131 Correct 363 ms 161144 KB Correct answer: answer = 277966670
132 Correct 259 ms 160944 KB Correct answer: answer = 2500900082
133 Correct 94 ms 159408 KB Correct answer: answer = 301248349636
134 Correct 207 ms 158920 KB Correct answer: answer = 14118891
135 Correct 79 ms 159392 KB Correct answer: answer = 14384977265
136 Correct 74 ms 159356 KB Correct answer: answer = 3681368330
137 Correct 86 ms 159380 KB Correct answer: answer = 2720316816
138 Correct 101 ms 161900 KB Correct answer: answer = 999976000144
139 Correct 92 ms 161924 KB Correct answer: answer = 999856102410
140 Correct 86 ms 161948 KB Correct answer: answer = 999958401531
141 Correct 86 ms 161928 KB Correct answer: answer = 999769649944
142 Correct 87 ms 161856 KB Correct answer: answer = 999874525918
143 Correct 434 ms 164756 KB Correct answer: answer = 6050000000
144 Correct 632 ms 164880 KB Correct answer: answer = 1112500000
145 Correct 230 ms 162024 KB Correct answer: answer = 4294967296
146 Correct 465 ms 162320 KB Correct answer: answer = 87652406
147 Correct 477 ms 162500 KB Correct answer: answer = 6297664
148 Correct 462 ms 162412 KB Correct answer: answer = 196612
149 Correct 709 ms 165224 KB Correct answer: answer = 15015100
150 Correct 704 ms 165216 KB Correct answer: answer = 25000000
151 Correct 282 ms 164408 KB Correct answer: answer = 333230209550
152 Correct 460 ms 164352 KB Correct answer: answer = 917123769
153 Correct 514 ms 165204 KB Correct answer: answer = 95162
154 Correct 715 ms 165176 KB Correct answer: answer = 382616191
155 Correct 702 ms 165304 KB Correct answer: answer = 990033333400
156 Correct 685 ms 165348 KB Correct answer: answer = 990000100000
157 Correct 482 ms 164696 KB Correct answer: answer = 749998188180
158 Correct 85 ms 161828 KB Correct answer: answer = 1000000000000
159 Correct 87 ms 161852 KB Correct answer: answer = 999988000036
160 Correct 95 ms 161852 KB Correct answer: answer = 744929274393
161 Correct 77 ms 160996 KB Correct answer: answer = 2
162 Correct 702 ms 165224 KB Correct answer: answer = 1300024
163 Correct 796 ms 164820 KB Correct answer: answer = 5000700010
164 Correct 163 ms 161884 KB Correct answer: answer = 354997100800
165 Correct 357 ms 161040 KB Correct answer: answer = 257000
166 Correct 419 ms 161220 KB Correct answer: answer = 3765323
167 Correct 383 ms 161172 KB Correct answer: answer = 1525903
168 Correct 96 ms 161956 KB Correct answer: answer = 67618137730
169 Correct 100 ms 161976 KB Correct answer: answer = 12656680171
170 Correct 110 ms 161972 KB Correct answer: answer = 579831736
171 Correct 231 ms 162928 KB Correct answer: answer = 23605611
172 Correct 108 ms 161920 KB Correct answer: answer = 7052481200
173 Correct 146 ms 162032 KB Correct answer: answer = 1314039500
174 Correct 199 ms 162612 KB Correct answer: answer = 302484000
175 Correct 398 ms 164528 KB Correct answer: answer = 52348480