oj.uz

Submission #681801

# Submission time Handle Problem Language Result Execution time Memory
681801 2023-01-14T12:01:24 Z cadmiumsky Aliens (IOI16_aliens) C++14
100 / 100
 1125 ms 70664 KB 
#include "aliens.h"
#include <bits/stdc++.h>

#warning fa cu ll
using namespace std;

using ll = long long;

#define int ll
#define sz(x) (int)(x).size()

const int nmax = 1e6 + 5;

struct line {
  int chosen = 0;
  ll dp = 0, b = (ll)nmax * nmax;
  line(int x = 0, ll y = (ll)nmax * nmax, ll z = (ll)nmax * nmax): chosen(x), dp(y), b(z) {;}
  ll operator()(const ll& x) const { return b * x + dp; }
  bool operator()(const line& form, const line& cand) const {
    return (dp - form.dp) * (cand.b - b) > (dp - cand.dp) * (form.b - b) || ((dp - form.dp) * (cand.b - b) == (dp - cand.dp) * (form.b - b) && (b < cand.b || (b == cand.b && dp < cand.dp)));
  }
};

struct CHT {
  line cht[nmax];
  int ptr, lim;
  struct undo_info {
    line last;
    int ptrlast;
    int lstptr;
    int lstlim;
    undo_info(line a, int x, int y, int z): last(a), ptrlast(x), lstptr(y), lstlim(z) {;}
  };
  vector<undo_info> undost;
  int getT() { return sz(undost); }
  void push(line nv) {
    undost.emplace_back(line(), 0, ptr, lim);
    while(lim > 1 && nv(cht[lim - 2], cht[lim - 1])) lim--;
    
    undost.back().last = cht[lim];
    undost.back().ptrlast = lim;
    
    cht[lim++] = nv;
    ptr = min(lim - 1, ptr);
  }
  void undo() {
    cht[undost.back().ptrlast] = undost.back().last;
    ptr = undost.back().lstptr;
    lim = undost.back().lstlim;
    undost.pop_back();
    //cerr << "? " << lim << '\n';
  }
  void undo(int T) {
    assert(T >= 0);
    while(getT() > T)
      undo();
  }
  line query(int x) { // blea??
    while(ptr < lim - 1 && cht[ptr + 1](x) < cht[ptr](x))
      ptr++;
    //cerr << x << ' ' << cht[ptr](x) << '\t';
    //for(int i = 0; i < lim; i++)
      //cerr << cht[i](x) << ' ';
    //cerr << '\n';
    return cht[ptr];
  }
  void init() {
    undost.clear();
    ptr = 0;
    lim = 1;
    cht[0] = line(0, 0, 0);
    undost.reserve(nmax);
  }
} cht;

ll p2(ll x) { return x * x; }

line calculate(const vector<int>& height, ll C) {
  cht.init();
  
  vector<ll> dp(sz(height));
  vector<int> chosen(sz(height)), altern = height, st;
  st.reserve(sz(height));
  st.emplace_back(0);
  
  
  for(int i = 1; i < sz(altern); i++) altern[i] -= i;
  
  //for(auto x : height)
    //cerr << x << ' ';
  //cerr << '\n';
  //for(auto x : altern)
    //cerr << x << ' ';
  //cerr << '\n';
  
  for(int i = 1; i < sz(height); i++) {
    while(altern[st.back()] < altern[i])
      (height[st.back()]? cht.undo() : void()),
      st.pop_back();
    if(height[i] != 0) {
      cht.push(line(chosen[st.back()], (ll)dp[st.back()] - p2(st.back()) - (ll)2 * st.back() * (altern[i]), (ll)2 * (altern[i])));
      auto best = cht.query(i);
      dp[i] = best(i) + p2(i) + C;
      chosen[i] = best.chosen + 1;      
    }
    else {
      chosen[i] = chosen[i - 1], dp[i] = dp[i - 1];
    }
    //cerr << dp[i] << ' ';
    st.push_back(i);
    //for(auto x : st) cerr << x << ' ';
    //cerr << "\n---\n";
    //cerr << dp[i] << '\n';
  }
  //cerr << '\n';
  return line{chosen.back(), dp.back(), 0};
}

ll smenufromaliens(const vector<int>& height, int k) {
  ll lim = -1;
  for(ll i = (1LL << 40); i > 0; i >>= 1) {
    if(calculate(height, lim + i).chosen > k)
      lim += i;
  }
  return lim + 1;
}

ll take_photos(signed n, signed m, signed k, std::vector<signed> r, std::vector<signed> c) {
  if(n == 0) return 0;
  vector<int> height(m + 1);
  height[0] = m + 5;
  for(int i = 0; i < n; i++)
    r[i]++,
    c[i]++,
    height[max(r[i], c[i])] = max(height[max(r[i], c[i])], (ll)abs(r[i] - c[i]) + 1);
  while(height.back() == 0)
    height.pop_back();
  int lim = smenufromaliens(height, k);
  //int lim = 0;
  
  auto lol = calculate(height, lim);
  //cerr << lim << ' ' << lol.dp << ' ' << lol.chosen << ' ' << k << '\n';
  return (ll)lol.dp - (ll)lim * k;
}
#undef int

Compilation message

aliens.cpp:4:2: warning: #warning fa cu ll [-Wcpp]
    4 | #warning fa cu ll
      |  ^~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23764 KB Correct answer: answer = 4
2 Correct 11 ms 23764 KB Correct answer: answer = 4
3 Correct 11 ms 23764 KB Correct answer: answer = 4
4 Correct 11 ms 23792 KB Correct answer: answer = 12
5 Correct 11 ms 23788 KB Correct answer: answer = 52
6 Correct 11 ms 23712 KB Correct answer: answer = 210
7 Correct 12 ms 23764 KB Correct answer: answer = 88
8 Correct 10 ms 23712 KB Correct answer: answer = 7696
9 Correct 11 ms 23764 KB Correct answer: answer = 1
10 Correct 11 ms 23800 KB Correct answer: answer = 2374
11 Correct 12 ms 23748 KB Correct answer: answer = 9502
12 Correct 13 ms 23728 KB Correct answer: answer = 49
13 Correct 11 ms 23788 KB Correct answer: answer = 151
14 Correct 12 ms 23764 KB Correct answer: answer = 7550
15 Correct 11 ms 23792 KB Correct answer: answer = 7220
16 Correct 12 ms 23764 KB Correct answer: answer = 7550
17 Correct 10 ms 23764 KB Correct answer: answer = 10000
18 Correct 11 ms 23764 KB Correct answer: answer = 10000
19 Correct 11 ms 23764 KB Correct answer: answer = 624
20 Correct 11 ms 23760 KB Correct answer: answer = 10000

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Correct answer: answer = 1
2 Correct 13 ms 23764 KB Correct answer: answer = 4
3 Correct 11 ms 23764 KB Correct answer: answer = 1
4 Correct 13 ms 23764 KB Correct answer: answer = 5
5 Correct 11 ms 23764 KB Correct answer: answer = 41
6 Correct 11 ms 23788 KB Correct answer: answer = 71923
7 Correct 12 ms 23764 KB Correct answer: answer = 77137
8 Correct 11 ms 23764 KB Correct answer: answer = 764
9 Correct 15 ms 23748 KB Correct answer: answer = 250000
10 Correct 14 ms 23792 KB Correct answer: answer = 500
11 Correct 11 ms 23780 KB Correct answer: answer = 32
12 Correct 13 ms 23824 KB Correct answer: answer = 130050
13 Correct 14 ms 23892 KB Correct answer: answer = 5110
14 Correct 11 ms 23764 KB Correct answer: answer = 2626
15 Correct 11 ms 23784 KB Correct answer: answer = 796
16 Correct 11 ms 23792 KB Correct answer: answer = 7580
17 Correct 11 ms 23764 KB Correct answer: answer = 1904
18 Correct 11 ms 23764 KB Correct answer: answer = 996004
19 Correct 12 ms 23788 KB Correct answer: answer = 38817
20 Correct 12 ms 23780 KB Correct answer: answer = 4096
21 Correct 12 ms 23764 KB Correct answer: answer = 1
22 Correct 11 ms 23784 KB Correct answer: answer = 1
23 Correct 11 ms 23740 KB Correct answer: answer = 2040
24 Correct 12 ms 23764 KB Correct answer: answer = 2

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23764 KB Correct answer: answer = 4
2 Correct 11 ms 23764 KB Correct answer: answer = 4
3 Correct 11 ms 23764 KB Correct answer: answer = 4
4 Correct 11 ms 23792 KB Correct answer: answer = 12
5 Correct 11 ms 23788 KB Correct answer: answer = 52
6 Correct 11 ms 23712 KB Correct answer: answer = 210
7 Correct 12 ms 23764 KB Correct answer: answer = 88
8 Correct 10 ms 23712 KB Correct answer: answer = 7696
9 Correct 11 ms 23764 KB Correct answer: answer = 1
10 Correct 11 ms 23800 KB Correct answer: answer = 2374
11 Correct 12 ms 23748 KB Correct answer: answer = 9502
12 Correct 13 ms 23728 KB Correct answer: answer = 49
13 Correct 11 ms 23788 KB Correct answer: answer = 151
14 Correct 12 ms 23764 KB Correct answer: answer = 7550
15 Correct 11 ms 23792 KB Correct answer: answer = 7220
16 Correct 12 ms 23764 KB Correct answer: answer = 7550
17 Correct 10 ms 23764 KB Correct answer: answer = 10000
18 Correct 11 ms 23764 KB Correct answer: answer = 10000
19 Correct 11 ms 23764 KB Correct answer: answer = 624
20 Correct 11 ms 23760 KB Correct answer: answer = 10000
21 Correct 12 ms 23764 KB Correct answer: answer = 1
22 Correct 13 ms 23764 KB Correct answer: answer = 4
23 Correct 11 ms 23764 KB Correct answer: answer = 1
24 Correct 13 ms 23764 KB Correct answer: answer = 5
25 Correct 11 ms 23764 KB Correct answer: answer = 41
26 Correct 11 ms 23788 KB Correct answer: answer = 71923
27 Correct 12 ms 23764 KB Correct answer: answer = 77137
28 Correct 11 ms 23764 KB Correct answer: answer = 764
29 Correct 15 ms 23748 KB Correct answer: answer = 250000
30 Correct 14 ms 23792 KB Correct answer: answer = 500
31 Correct 11 ms 23780 KB Correct answer: answer = 32
32 Correct 13 ms 23824 KB Correct answer: answer = 130050
33 Correct 14 ms 23892 KB Correct answer: answer = 5110
34 Correct 11 ms 23764 KB Correct answer: answer = 2626
35 Correct 11 ms 23784 KB Correct answer: answer = 796
36 Correct 11 ms 23792 KB Correct answer: answer = 7580
37 Correct 11 ms 23764 KB Correct answer: answer = 1904
38 Correct 11 ms 23764 KB Correct answer: answer = 996004
39 Correct 12 ms 23788 KB Correct answer: answer = 38817
40 Correct 12 ms 23780 KB Correct answer: answer = 4096
41 Correct 12 ms 23764 KB Correct answer: answer = 1
42 Correct 11 ms 23784 KB Correct answer: answer = 1
43 Correct 11 ms 23740 KB Correct answer: answer = 2040
44 Correct 12 ms 23764 KB Correct answer: answer = 2
45 Correct 10 ms 23764 KB Correct answer: answer = 4
46 Correct 11 ms 23768 KB Correct answer: answer = 9
47 Correct 11 ms 23804 KB Correct answer: answer = 9
48 Correct 11 ms 23784 KB Correct answer: answer = 21
49 Correct 12 ms 23764 KB Correct answer: answer = 71
50 Correct 13 ms 23788 KB Correct answer: answer = 77
51 Correct 10 ms 23764 KB Correct answer: answer = 400
52 Correct 11 ms 23764 KB Correct answer: answer = 996004
53 Correct 12 ms 23788 KB Correct answer: answer = 997310
54 Correct 13 ms 23784 KB Correct answer: answer = 990781
55 Correct 13 ms 23788 KB Correct answer: answer = 996545
56 Correct 10 ms 23780 KB Correct answer: answer = 484
57 Correct 10 ms 23772 KB Correct answer: answer = 484
58 Correct 12 ms 23768 KB Correct answer: answer = 63501
59 Correct 11 ms 23752 KB Correct answer: answer = 323501
60 Correct 12 ms 23820 KB Correct answer: answer = 752500
61 Correct 12 ms 23852 KB Correct answer: answer = 761480
62 Correct 11 ms 23764 KB Correct answer: answer = 758932
63 Correct 11 ms 23740 KB Correct answer: answer = 1000000
64 Correct 13 ms 23792 KB Correct answer: answer = 750500
65 Correct 12 ms 23768 KB Correct answer: answer = 1000000
66 Correct 11 ms 23776 KB Correct answer: answer = 250000
67 Correct 11 ms 23764 KB Correct answer: answer = 250000
68 Correct 11 ms 23840 KB Correct answer: answer = 1000000
69 Correct 12 ms 23784 KB Correct answer: answer = 994009
70 Correct 14 ms 23764 KB Correct answer: answer = 59315
71 Correct 14 ms 23764 KB Correct answer: answer = 25454
72 Correct 12 ms 23764 KB Correct answer: answer = 1504
73 Correct 11 ms 23828 KB Correct answer: answer = 37486
74 Correct 11 ms 23844 KB Correct answer: answer = 4284
75 Correct 11 ms 23844 KB Correct answer: answer = 158008
76 Correct 11 ms 23764 KB Correct answer: answer = 51860
77 Correct 12 ms 23784 KB Correct answer: answer = 12985

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23764 KB Correct answer: answer = 4
2 Correct 11 ms 23764 KB Correct answer: answer = 4
3 Correct 11 ms 23764 KB Correct answer: answer = 4
4 Correct 11 ms 23792 KB Correct answer: answer = 12
5 Correct 11 ms 23788 KB Correct answer: answer = 52
6 Correct 11 ms 23712 KB Correct answer: answer = 210
7 Correct 12 ms 23764 KB Correct answer: answer = 88
8 Correct 10 ms 23712 KB Correct answer: answer = 7696
9 Correct 11 ms 23764 KB Correct answer: answer = 1
10 Correct 11 ms 23800 KB Correct answer: answer = 2374
11 Correct 12 ms 23748 KB Correct answer: answer = 9502
12 Correct 13 ms 23728 KB Correct answer: answer = 49
13 Correct 11 ms 23788 KB Correct answer: answer = 151
14 Correct 12 ms 23764 KB Correct answer: answer = 7550
15 Correct 11 ms 23792 KB Correct answer: answer = 7220
16 Correct 12 ms 23764 KB Correct answer: answer = 7550
17 Correct 10 ms 23764 KB Correct answer: answer = 10000
18 Correct 11 ms 23764 KB Correct answer: answer = 10000
19 Correct 11 ms 23764 KB Correct answer: answer = 624
20 Correct 11 ms 23760 KB Correct answer: answer = 10000
21 Correct 12 ms 23764 KB Correct answer: answer = 1
22 Correct 13 ms 23764 KB Correct answer: answer = 4
23 Correct 11 ms 23764 KB Correct answer: answer = 1
24 Correct 13 ms 23764 KB Correct answer: answer = 5
25 Correct 11 ms 23764 KB Correct answer: answer = 41
26 Correct 11 ms 23788 KB Correct answer: answer = 71923
27 Correct 12 ms 23764 KB Correct answer: answer = 77137
28 Correct 11 ms 23764 KB Correct answer: answer = 764
29 Correct 15 ms 23748 KB Correct answer: answer = 250000
30 Correct 14 ms 23792 KB Correct answer: answer = 500
31 Correct 11 ms 23780 KB Correct answer: answer = 32
32 Correct 13 ms 23824 KB Correct answer: answer = 130050
33 Correct 14 ms 23892 KB Correct answer: answer = 5110
34 Correct 11 ms 23764 KB Correct answer: answer = 2626
35 Correct 11 ms 23784 KB Correct answer: answer = 796
36 Correct 11 ms 23792 KB Correct answer: answer = 7580
37 Correct 11 ms 23764 KB Correct answer: answer = 1904
38 Correct 11 ms 23764 KB Correct answer: answer = 996004
39 Correct 12 ms 23788 KB Correct answer: answer = 38817
40 Correct 12 ms 23780 KB Correct answer: answer = 4096
41 Correct 12 ms 23764 KB Correct answer: answer = 1
42 Correct 11 ms 23784 KB Correct answer: answer = 1
43 Correct 11 ms 23740 KB Correct answer: answer = 2040
44 Correct 12 ms 23764 KB Correct answer: answer = 2
45 Correct 10 ms 23764 KB Correct answer: answer = 4
46 Correct 11 ms 23768 KB Correct answer: answer = 9
47 Correct 11 ms 23804 KB Correct answer: answer = 9
48 Correct 11 ms 23784 KB Correct answer: answer = 21
49 Correct 12 ms 23764 KB Correct answer: answer = 71
50 Correct 13 ms 23788 KB Correct answer: answer = 77
51 Correct 10 ms 23764 KB Correct answer: answer = 400
52 Correct 11 ms 23764 KB Correct answer: answer = 996004
53 Correct 12 ms 23788 KB Correct answer: answer = 997310
54 Correct 13 ms 23784 KB Correct answer: answer = 990781
55 Correct 13 ms 23788 KB Correct answer: answer = 996545
56 Correct 10 ms 23780 KB Correct answer: answer = 484
57 Correct 10 ms 23772 KB Correct answer: answer = 484
58 Correct 12 ms 23768 KB Correct answer: answer = 63501
59 Correct 11 ms 23752 KB Correct answer: answer = 323501
60 Correct 12 ms 23820 KB Correct answer: answer = 752500
61 Correct 12 ms 23852 KB Correct answer: answer = 761480
62 Correct 11 ms 23764 KB Correct answer: answer = 758932
63 Correct 11 ms 23740 KB Correct answer: answer = 1000000
64 Correct 13 ms 23792 KB Correct answer: answer = 750500
65 Correct 12 ms 23768 KB Correct answer: answer = 1000000
66 Correct 11 ms 23776 KB Correct answer: answer = 250000
67 Correct 11 ms 23764 KB Correct answer: answer = 250000
68 Correct 11 ms 23840 KB Correct answer: answer = 1000000
69 Correct 12 ms 23784 KB Correct answer: answer = 994009
70 Correct 14 ms 23764 KB Correct answer: answer = 59315
71 Correct 14 ms 23764 KB Correct answer: answer = 25454
72 Correct 12 ms 23764 KB Correct answer: answer = 1504
73 Correct 11 ms 23828 KB Correct answer: answer = 37486
74 Correct 11 ms 23844 KB Correct answer: answer = 4284
75 Correct 11 ms 23844 KB Correct answer: answer = 158008
76 Correct 11 ms 23764 KB Correct answer: answer = 51860
77 Correct 12 ms 23784 KB Correct answer: answer = 12985
78 Correct 871 ms 55636 KB Correct answer: answer = 997864126212
79 Correct 885 ms 55628 KB Correct answer: answer = 998608411647
80 Correct 872 ms 55516 KB Correct answer: answer = 995265560477
81 Correct 15 ms 24260 KB Correct answer: answer = 10125000
82 Correct 15 ms 24248 KB Correct answer: answer = 2291668
83 Correct 13 ms 23928 KB Correct answer: answer = 42388
84 Correct 12 ms 23988 KB Correct answer: answer = 10318
85 Correct 14 ms 24020 KB Correct answer: answer = 3416
86 Correct 984 ms 63432 KB Correct answer: answer = 331708193881
87 Correct 1010 ms 63352 KB Correct answer: answer = 2861193756
88 Correct 958 ms 63292 KB Correct answer: answer = 114646930
89 Correct 16 ms 24276 KB Correct answer: answer = 9280921
90 Correct 1034 ms 63292 KB Correct answer: answer = 999984053400
91 Correct 970 ms 59416 KB Correct answer: answer = 750935949134
92 Correct 1016 ms 63072 KB Correct answer: answer = 1000000000000
93 Correct 962 ms 59348 KB Correct answer: answer = 998762383161
94 Correct 961 ms 62872 KB Correct answer: answer = 23017412908
95 Correct 848 ms 55212 KB Correct answer: answer = 728143410622
96 Correct 993 ms 63100 KB Correct answer: answer = 2
97 Correct 955 ms 63400 KB Correct answer: answer = 1824916
98 Correct 103 ms 28068 KB Correct answer: answer = 10680029
99 Correct 94 ms 28056 KB Correct answer: answer = 18351700
100 Correct 969 ms 63456 KB Correct answer: answer = 16040026
101 Correct 512 ms 47644 KB Correct answer: answer = 253968628325
102 Correct 14 ms 24020 KB Correct answer: answer = 10267
103 Correct 472 ms 44140 KB Correct answer: answer = 2582408
104 Correct 934 ms 60216 KB Correct answer: answer = 78024964781
105 Correct 936 ms 60896 KB Correct answer: answer = 9866346457
106 Correct 950 ms 59548 KB Correct answer: answer = 3327720949
107 Correct 896 ms 55608 KB Correct answer: answer = 86064128360
108 Correct 883 ms 55696 KB Correct answer: answer = 12698259150
109 Correct 893 ms 56680 KB Correct answer: answer = 1185259288

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23764 KB Correct answer: answer = 4
2 Correct 11 ms 23764 KB Correct answer: answer = 4
3 Correct 11 ms 23764 KB Correct answer: answer = 4
4 Correct 11 ms 23792 KB Correct answer: answer = 12
5 Correct 11 ms 23788 KB Correct answer: answer = 52
6 Correct 11 ms 23712 KB Correct answer: answer = 210
7 Correct 12 ms 23764 KB Correct answer: answer = 88
8 Correct 10 ms 23712 KB Correct answer: answer = 7696
9 Correct 11 ms 23764 KB Correct answer: answer = 1
10 Correct 11 ms 23800 KB Correct answer: answer = 2374
11 Correct 12 ms 23748 KB Correct answer: answer = 9502
12 Correct 13 ms 23728 KB Correct answer: answer = 49
13 Correct 11 ms 23788 KB Correct answer: answer = 151
14 Correct 12 ms 23764 KB Correct answer: answer = 7550
15 Correct 11 ms 23792 KB Correct answer: answer = 7220
16 Correct 12 ms 23764 KB Correct answer: answer = 7550
17 Correct 10 ms 23764 KB Correct answer: answer = 10000
18 Correct 11 ms 23764 KB Correct answer: answer = 10000
19 Correct 11 ms 23764 KB Correct answer: answer = 624
20 Correct 11 ms 23760 KB Correct answer: answer = 10000
21 Correct 12 ms 23764 KB Correct answer: answer = 1
22 Correct 13 ms 23764 KB Correct answer: answer = 4
23 Correct 11 ms 23764 KB Correct answer: answer = 1
24 Correct 13 ms 23764 KB Correct answer: answer = 5
25 Correct 11 ms 23764 KB Correct answer: answer = 41
26 Correct 11 ms 23788 KB Correct answer: answer = 71923
27 Correct 12 ms 23764 KB Correct answer: answer = 77137
28 Correct 11 ms 23764 KB Correct answer: answer = 764
29 Correct 15 ms 23748 KB Correct answer: answer = 250000
30 Correct 14 ms 23792 KB Correct answer: answer = 500
31 Correct 11 ms 23780 KB Correct answer: answer = 32
32 Correct 13 ms 23824 KB Correct answer: answer = 130050
33 Correct 14 ms 23892 KB Correct answer: answer = 5110
34 Correct 11 ms 23764 KB Correct answer: answer = 2626
35 Correct 11 ms 23784 KB Correct answer: answer = 796
36 Correct 11 ms 23792 KB Correct answer: answer = 7580
37 Correct 11 ms 23764 KB Correct answer: answer = 1904
38 Correct 11 ms 23764 KB Correct answer: answer = 996004
39 Correct 12 ms 23788 KB Correct answer: answer = 38817
40 Correct 12 ms 23780 KB Correct answer: answer = 4096
41 Correct 12 ms 23764 KB Correct answer: answer = 1
42 Correct 11 ms 23784 KB Correct answer: answer = 1
43 Correct 11 ms 23740 KB Correct answer: answer = 2040
44 Correct 12 ms 23764 KB Correct answer: answer = 2
45 Correct 10 ms 23764 KB Correct answer: answer = 4
46 Correct 11 ms 23768 KB Correct answer: answer = 9
47 Correct 11 ms 23804 KB Correct answer: answer = 9
48 Correct 11 ms 23784 KB Correct answer: answer = 21
49 Correct 12 ms 23764 KB Correct answer: answer = 71
50 Correct 13 ms 23788 KB Correct answer: answer = 77
51 Correct 10 ms 23764 KB Correct answer: answer = 400
52 Correct 11 ms 23764 KB Correct answer: answer = 996004
53 Correct 12 ms 23788 KB Correct answer: answer = 997310
54 Correct 13 ms 23784 KB Correct answer: answer = 990781
55 Correct 13 ms 23788 KB Correct answer: answer = 996545
56 Correct 10 ms 23780 KB Correct answer: answer = 484
57 Correct 10 ms 23772 KB Correct answer: answer = 484
58 Correct 12 ms 23768 KB Correct answer: answer = 63501
59 Correct 11 ms 23752 KB Correct answer: answer = 323501
60 Correct 12 ms 23820 KB Correct answer: answer = 752500
61 Correct 12 ms 23852 KB Correct answer: answer = 761480
62 Correct 11 ms 23764 KB Correct answer: answer = 758932
63 Correct 11 ms 23740 KB Correct answer: answer = 1000000
64 Correct 13 ms 23792 KB Correct answer: answer = 750500
65 Correct 12 ms 23768 KB Correct answer: answer = 1000000
66 Correct 11 ms 23776 KB Correct answer: answer = 250000
67 Correct 11 ms 23764 KB Correct answer: answer = 250000
68 Correct 11 ms 23840 KB Correct answer: answer = 1000000
69 Correct 12 ms 23784 KB Correct answer: answer = 994009
70 Correct 14 ms 23764 KB Correct answer: answer = 59315
71 Correct 14 ms 23764 KB Correct answer: answer = 25454
72 Correct 12 ms 23764 KB Correct answer: answer = 1504
73 Correct 11 ms 23828 KB Correct answer: answer = 37486
74 Correct 11 ms 23844 KB Correct answer: answer = 4284
75 Correct 11 ms 23844 KB Correct answer: answer = 158008
76 Correct 11 ms 23764 KB Correct answer: answer = 51860
77 Correct 12 ms 23784 KB Correct answer: answer = 12985
78 Correct 871 ms 55636 KB Correct answer: answer = 997864126212
79 Correct 885 ms 55628 KB Correct answer: answer = 998608411647
80 Correct 872 ms 55516 KB Correct answer: answer = 995265560477
81 Correct 15 ms 24260 KB Correct answer: answer = 10125000
82 Correct 15 ms 24248 KB Correct answer: answer = 2291668
83 Correct 13 ms 23928 KB Correct answer: answer = 42388
84 Correct 12 ms 23988 KB Correct answer: answer = 10318
85 Correct 14 ms 24020 KB Correct answer: answer = 3416
86 Correct 984 ms 63432 KB Correct answer: answer = 331708193881
87 Correct 1010 ms 63352 KB Correct answer: answer = 2861193756
88 Correct 958 ms 63292 KB Correct answer: answer = 114646930
89 Correct 16 ms 24276 KB Correct answer: answer = 9280921
90 Correct 1034 ms 63292 KB Correct answer: answer = 999984053400
91 Correct 970 ms 59416 KB Correct answer: answer = 750935949134
92 Correct 1016 ms 63072 KB Correct answer: answer = 1000000000000
93 Correct 962 ms 59348 KB Correct answer: answer = 998762383161
94 Correct 961 ms 62872 KB Correct answer: answer = 23017412908
95 Correct 848 ms 55212 KB Correct answer: answer = 728143410622
96 Correct 993 ms 63100 KB Correct answer: answer = 2
97 Correct 955 ms 63400 KB Correct answer: answer = 1824916
98 Correct 103 ms 28068 KB Correct answer: answer = 10680029
99 Correct 94 ms 28056 KB Correct answer: answer = 18351700
100 Correct 969 ms 63456 KB Correct answer: answer = 16040026
101 Correct 512 ms 47644 KB Correct answer: answer = 253968628325
102 Correct 14 ms 24020 KB Correct answer: answer = 10267
103 Correct 472 ms 44140 KB Correct answer: answer = 2582408
104 Correct 934 ms 60216 KB Correct answer: answer = 78024964781
105 Correct 936 ms 60896 KB Correct answer: answer = 9866346457
106 Correct 950 ms 59548 KB Correct answer: answer = 3327720949
107 Correct 896 ms 55608 KB Correct answer: answer = 86064128360
108 Correct 883 ms 55696 KB Correct answer: answer = 12698259150
109 Correct 893 ms 56680 KB Correct answer: answer = 1185259288
110 Correct 963 ms 56876 KB Correct answer: answer = 999889968863
111 Correct 968 ms 56768 KB Correct answer: answer = 999861384931
112 Correct 958 ms 56960 KB Correct answer: answer = 999811809929
113 Correct 960 ms 56912 KB Correct answer: answer = 999869756441
114 Correct 92 ms 30148 KB Correct answer: answer = 1700000000
115 Correct 94 ms 29900 KB Correct answer: answer = 131666670
116 Correct 30 ms 25556 KB Correct answer: answer = 89478486
117 Correct 29 ms 25556 KB Correct answer: answer = 4971040
118 Correct 31 ms 25592 KB Correct answer: answer = 2711494
119 Correct 84 ms 29536 KB Correct answer: answer = 25252530
120 Correct 90 ms 29588 KB Correct answer: answer = 62500000
121 Correct 1044 ms 66724 KB Correct answer: answer = 333175097780
122 Correct 1054 ms 66776 KB Correct answer: answer = 33121180179
123 Correct 1052 ms 66852 KB Correct answer: answer = 9802314015
124 Correct 76 ms 29576 KB Correct answer: answer = 32567551
125 Correct 1075 ms 66400 KB Correct answer: answer = 997525000000
126 Correct 1071 ms 62936 KB Correct answer: answer = 752723538884
127 Correct 1047 ms 64136 KB Correct answer: answer = 1000000000000
128 Correct 1045 ms 60648 KB Correct answer: answer = 999978000121
129 Correct 959 ms 56720 KB Correct answer: answer = 745986144735
130 Correct 967 ms 64132 KB Correct answer: answer = 2
131 Correct 996 ms 66748 KB Correct answer: answer = 277966670
132 Correct 996 ms 66696 KB Correct answer: answer = 2500900082
133 Correct 617 ms 50228 KB Correct answer: answer = 301248349636
134 Correct 72 ms 27116 KB Correct answer: answer = 14118891
135 Correct 464 ms 44472 KB Correct answer: answer = 14384977265
136 Correct 1125 ms 62036 KB Correct answer: answer = 3681368330
137 Correct 1025 ms 61392 KB Correct answer: answer = 2720316816

Subtask #6
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23764 KB Correct answer: answer = 4
2 Correct 11 ms 23764 KB Correct answer: answer = 4
3 Correct 11 ms 23764 KB Correct answer: answer = 4
4 Correct 11 ms 23792 KB Correct answer: answer = 12
5 Correct 11 ms 23788 KB Correct answer: answer = 52
6 Correct 11 ms 23712 KB Correct answer: answer = 210
7 Correct 12 ms 23764 KB Correct answer: answer = 88
8 Correct 10 ms 23712 KB Correct answer: answer = 7696
9 Correct 11 ms 23764 KB Correct answer: answer = 1
10 Correct 11 ms 23800 KB Correct answer: answer = 2374
11 Correct 12 ms 23748 KB Correct answer: answer = 9502
12 Correct 13 ms 23728 KB Correct answer: answer = 49
13 Correct 11 ms 23788 KB Correct answer: answer = 151
14 Correct 12 ms 23764 KB Correct answer: answer = 7550
15 Correct 11 ms 23792 KB Correct answer: answer = 7220
16 Correct 12 ms 23764 KB Correct answer: answer = 7550
17 Correct 10 ms 23764 KB Correct answer: answer = 10000
18 Correct 11 ms 23764 KB Correct answer: answer = 10000
19 Correct 11 ms 23764 KB Correct answer: answer = 624
20 Correct 11 ms 23760 KB Correct answer: answer = 10000
21 Correct 12 ms 23764 KB Correct answer: answer = 1
22 Correct 13 ms 23764 KB Correct answer: answer = 4
23 Correct 11 ms 23764 KB Correct answer: answer = 1
24 Correct 13 ms 23764 KB Correct answer: answer = 5
25 Correct 11 ms 23764 KB Correct answer: answer = 41
26 Correct 11 ms 23788 KB Correct answer: answer = 71923
27 Correct 12 ms 23764 KB Correct answer: answer = 77137
28 Correct 11 ms 23764 KB Correct answer: answer = 764
29 Correct 15 ms 23748 KB Correct answer: answer = 250000
30 Correct 14 ms 23792 KB Correct answer: answer = 500
31 Correct 11 ms 23780 KB Correct answer: answer = 32
32 Correct 13 ms 23824 KB Correct answer: answer = 130050
33 Correct 14 ms 23892 KB Correct answer: answer = 5110
34 Correct 11 ms 23764 KB Correct answer: answer = 2626
35 Correct 11 ms 23784 KB Correct answer: answer = 796
36 Correct 11 ms 23792 KB Correct answer: answer = 7580
37 Correct 11 ms 23764 KB Correct answer: answer = 1904
38 Correct 11 ms 23764 KB Correct answer: answer = 996004
39 Correct 12 ms 23788 KB Correct answer: answer = 38817
40 Correct 12 ms 23780 KB Correct answer: answer = 4096
41 Correct 12 ms 23764 KB Correct answer: answer = 1
42 Correct 11 ms 23784 KB Correct answer: answer = 1
43 Correct 11 ms 23740 KB Correct answer: answer = 2040
44 Correct 12 ms 23764 KB Correct answer: answer = 2
45 Correct 10 ms 23764 KB Correct answer: answer = 4
46 Correct 11 ms 23768 KB Correct answer: answer = 9
47 Correct 11 ms 23804 KB Correct answer: answer = 9
48 Correct 11 ms 23784 KB Correct answer: answer = 21
49 Correct 12 ms 23764 KB Correct answer: answer = 71
50 Correct 13 ms 23788 KB Correct answer: answer = 77
51 Correct 10 ms 23764 KB Correct answer: answer = 400
52 Correct 11 ms 23764 KB Correct answer: answer = 996004
53 Correct 12 ms 23788 KB Correct answer: answer = 997310
54 Correct 13 ms 23784 KB Correct answer: answer = 990781
55 Correct 13 ms 23788 KB Correct answer: answer = 996545
56 Correct 10 ms 23780 KB Correct answer: answer = 484
57 Correct 10 ms 23772 KB Correct answer: answer = 484
58 Correct 12 ms 23768 KB Correct answer: answer = 63501
59 Correct 11 ms 23752 KB Correct answer: answer = 323501
60 Correct 12 ms 23820 KB Correct answer: answer = 752500
61 Correct 12 ms 23852 KB Correct answer: answer = 761480
62 Correct 11 ms 23764 KB Correct answer: answer = 758932
63 Correct 11 ms 23740 KB Correct answer: answer = 1000000
64 Correct 13 ms 23792 KB Correct answer: answer = 750500
65 Correct 12 ms 23768 KB Correct answer: answer = 1000000
66 Correct 11 ms 23776 KB Correct answer: answer = 250000
67 Correct 11 ms 23764 KB Correct answer: answer = 250000
68 Correct 11 ms 23840 KB Correct answer: answer = 1000000
69 Correct 12 ms 23784 KB Correct answer: answer = 994009
70 Correct 14 ms 23764 KB Correct answer: answer = 59315
71 Correct 14 ms 23764 KB Correct answer: answer = 25454
72 Correct 12 ms 23764 KB Correct answer: answer = 1504
73 Correct 11 ms 23828 KB Correct answer: answer = 37486
74 Correct 11 ms 23844 KB Correct answer: answer = 4284
75 Correct 11 ms 23844 KB Correct answer: answer = 158008
76 Correct 11 ms 23764 KB Correct answer: answer = 51860
77 Correct 12 ms 23784 KB Correct answer: answer = 12985
78 Correct 871 ms 55636 KB Correct answer: answer = 997864126212
79 Correct 885 ms 55628 KB Correct answer: answer = 998608411647
80 Correct 872 ms 55516 KB Correct answer: answer = 995265560477
81 Correct 15 ms 24260 KB Correct answer: answer = 10125000
82 Correct 15 ms 24248 KB Correct answer: answer = 2291668
83 Correct 13 ms 23928 KB Correct answer: answer = 42388
84 Correct 12 ms 23988 KB Correct answer: answer = 10318
85 Correct 14 ms 24020 KB Correct answer: answer = 3416
86 Correct 984 ms 63432 KB Correct answer: answer = 331708193881
87 Correct 1010 ms 63352 KB Correct answer: answer = 2861193756
88 Correct 958 ms 63292 KB Correct answer: answer = 114646930
89 Correct 16 ms 24276 KB Correct answer: answer = 9280921
90 Correct 1034 ms 63292 KB Correct answer: answer = 999984053400
91 Correct 970 ms 59416 KB Correct answer: answer = 750935949134
92 Correct 1016 ms 63072 KB Correct answer: answer = 1000000000000
93 Correct 962 ms 59348 KB Correct answer: answer = 998762383161
94 Correct 961 ms 62872 KB Correct answer: answer = 23017412908
95 Correct 848 ms 55212 KB Correct answer: answer = 728143410622
96 Correct 993 ms 63100 KB Correct answer: answer = 2
97 Correct 955 ms 63400 KB Correct answer: answer = 1824916
98 Correct 103 ms 28068 KB Correct answer: answer = 10680029
99 Correct 94 ms 28056 KB Correct answer: answer = 18351700
100 Correct 969 ms 63456 KB Correct answer: answer = 16040026
101 Correct 512 ms 47644 KB Correct answer: answer = 253968628325
102 Correct 14 ms 24020 KB Correct answer: answer = 10267
103 Correct 472 ms 44140 KB Correct answer: answer = 2582408
104 Correct 934 ms 60216 KB Correct answer: answer = 78024964781
105 Correct 936 ms 60896 KB Correct answer: answer = 9866346457
106 Correct 950 ms 59548 KB Correct answer: answer = 3327720949
107 Correct 896 ms 55608 KB Correct answer: answer = 86064128360
108 Correct 883 ms 55696 KB Correct answer: answer = 12698259150
109 Correct 893 ms 56680 KB Correct answer: answer = 1185259288
110 Correct 963 ms 56876 KB Correct answer: answer = 999889968863
111 Correct 968 ms 56768 KB Correct answer: answer = 999861384931
112 Correct 958 ms 56960 KB Correct answer: answer = 999811809929
113 Correct 960 ms 56912 KB Correct answer: answer = 999869756441
114 Correct 92 ms 30148 KB Correct answer: answer = 1700000000
115 Correct 94 ms 29900 KB Correct answer: answer = 131666670
116 Correct 30 ms 25556 KB Correct answer: answer = 89478486
117 Correct 29 ms 25556 KB Correct answer: answer = 4971040
118 Correct 31 ms 25592 KB Correct answer: answer = 2711494
119 Correct 84 ms 29536 KB Correct answer: answer = 25252530
120 Correct 90 ms 29588 KB Correct answer: answer = 62500000
121 Correct 1044 ms 66724 KB Correct answer: answer = 333175097780
122 Correct 1054 ms 66776 KB Correct answer: answer = 33121180179
123 Correct 1052 ms 66852 KB Correct answer: answer = 9802314015
124 Correct 76 ms 29576 KB Correct answer: answer = 32567551
125 Correct 1075 ms 66400 KB Correct answer: answer = 997525000000
126 Correct 1071 ms 62936 KB Correct answer: answer = 752723538884
127 Correct 1047 ms 64136 KB Correct answer: answer = 1000000000000
128 Correct 1045 ms 60648 KB Correct answer: answer = 999978000121
129 Correct 959 ms 56720 KB Correct answer: answer = 745986144735
130 Correct 967 ms 64132 KB Correct answer: answer = 2
131 Correct 996 ms 66748 KB Correct answer: answer = 277966670
132 Correct 996 ms 66696 KB Correct answer: answer = 2500900082
133 Correct 617 ms 50228 KB Correct answer: answer = 301248349636
134 Correct 72 ms 27116 KB Correct answer: answer = 14118891
135 Correct 464 ms 44472 KB Correct answer: answer = 14384977265
136 Correct 1125 ms 62036 KB Correct answer: answer = 3681368330
137 Correct 1025 ms 61392 KB Correct answer: answer = 2720316816
138 Correct 1051 ms 58292 KB Correct answer: answer = 999976000144
139 Correct 1036 ms 58220 KB Correct answer: answer = 999856102410
140 Correct 1077 ms 58228 KB Correct answer: answer = 999958401531
141 Correct 1028 ms 58120 KB Correct answer: answer = 999769649944
142 Correct 1025 ms 58184 KB Correct answer: answer = 999874525918
143 Correct 182 ms 35576 KB Correct answer: answer = 6050000000
144 Correct 164 ms 35584 KB Correct answer: answer = 1112500000
145 Correct 108 ms 31308 KB Correct answer: answer = 4294967296
146 Correct 102 ms 31288 KB Correct answer: answer = 87652406
147 Correct 104 ms 31276 KB Correct answer: answer = 6297664
148 Correct 107 ms 31272 KB Correct answer: answer = 196612
149 Correct 167 ms 35152 KB Correct answer: answer = 15015100
150 Correct 148 ms 35220 KB Correct answer: answer = 25000000
151 Correct 1096 ms 70664 KB Correct answer: answer = 333230209550
152 Correct 1118 ms 70396 KB Correct answer: answer = 917123769
153 Correct 1093 ms 70548 KB Correct answer: answer = 95162
154 Correct 153 ms 35208 KB Correct answer: answer = 382616191
155 Correct 1090 ms 69980 KB Correct answer: answer = 990033333400
156 Correct 1050 ms 69776 KB Correct answer: answer = 990000100000
157 Correct 1079 ms 66476 KB Correct answer: answer = 749998188180
158 Correct 1049 ms 65216 KB Correct answer: answer = 1000000000000
159 Correct 1117 ms 62016 KB Correct answer: answer = 999988000036
160 Correct 1054 ms 58192 KB Correct answer: answer = 744929274393
161 Correct 962 ms 65108 KB Correct answer: answer = 2
162 Correct 992 ms 70524 KB Correct answer: answer = 1300024
163 Correct 1010 ms 70544 KB Correct answer: answer = 5000700010
164 Correct 717 ms 53244 KB Correct answer: answer = 354997100800
165 Correct 110 ms 30396 KB Correct answer: answer = 257000
166 Correct 618 ms 50812 KB Correct answer: answer = 3765323
167 Correct 290 ms 36476 KB Correct answer: answer = 1525903
168 Correct 745 ms 52336 KB Correct answer: answer = 67618137730
169 Correct 982 ms 60484 KB Correct answer: answer = 12656680171
170 Correct 1028 ms 62752 KB Correct answer: answer = 579831736
171 Correct 1084 ms 64880 KB Correct answer: answer = 23605611
172 Correct 995 ms 58520 KB Correct answer: answer = 7052481200
173 Correct 982 ms 59316 KB Correct answer: answer = 1314039500
174 Correct 964 ms 59740 KB Correct answer: answer = 302484000
175 Correct 980 ms 63412 KB Correct answer: answer = 52348480