oj.uz

Submission #172504

# Submission time Handle Problem Language Result Execution time Memory
172504 2020-01-01T19:08:40 Z golikovnik Aliens (IOI16_aliens) C++14
100 / 100
 552 ms 18468 KB 
#include <bits/stdc++.h>

using namespace std;

using i64 = long long;
using real_t = long double;

template <typename T>
struct line {
  T k, b;

  [[nodiscard]] T apply(T x) const {
    return k * x + b;
  }
};

template <typename T>
real_t inter(line<T> const& a, line<T> const& b) {
  return static_cast<real_t>(a.b - b.b) / (b.k - a.k);
}

template <typename T>
struct hull {
  struct item {
    line<T> l;
    real_t from;
    real_t to;
    int cnt;

    item(line<T> l_, real_t from_, real_t to_, int cnt_) : l(l_), from(from_)
    , to(to_), cnt(cnt_) {}
  };
  vector<item> lines;
  real_t const inf = 1e20;
  int ptr = 0;

  void add_line(line<T> const& l, int cnt) {
    while ((int) lines.size() >= 2 &&
           inter(l, lines.back().l) <=
           inter(lines.back().l, lines[lines.size() - 2].l)) {
      lines.pop_back();
    }
    if (lines.empty()) {
      lines.emplace_back(l, -inf, inf, cnt);
    } else {
      auto x = inter(l, lines.back().l);
      lines.back().to = x;
      lines.emplace_back(l, x, inf, cnt);
    }
  }

  pair<T, int> get(T x) {
    ptr = min(ptr, (int) lines.size() - 1);
    while (x > lines[ptr].to) {
      ++ptr;
    }
    return {lines[ptr].l.apply(x), lines[ptr].cnt};
  }
};

i64 take_photos(int n, int, int mx, vector<int> r, vector<int> c) {
  struct cell {
    int r, c;

    cell(int r_, int c_) : r(r_), c(c_) {}
  };
  vector<cell> a;
  {
    for (int i = 0; i < n; ++i) {
      if (r[i] < c[i]) {
        swap(r[i], c[i]);
      }
    }
    vector<int> p(n);
    iota(p.begin(), p.end(), 0);
    sort(p.begin(), p.end(), [&](int i, int j) {
      if (r[i] != r[j]) {
        return r[i] < r[j];
      }
      return c[i] > c[j];
    });
    for (int i = 0; i < n; ++i) {
      while (!a.empty() && a.back().c >= c[p[i]]) {
        a.pop_back();
      }
      a.emplace_back(r[p[i]], c[p[i]]);
    }
  }
  n = (int) a.size();
  mx = min(mx, n);
  auto calc = [&](i64 lam) -> pair<i64, int> {
    auto sqr = [](i64 x) {
      return x * x;
    };
    hull<i64> cht;
    i64 cur = 0;
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
      auto ci = !i ? 0 : sqr(
              max<i64>(0, a[i - 1].r - a[i].c + 1));
      cht.add_line({-2 * a[i].c, sqr(a[i].c) + cur - ci},
                   cnt);
      auto res = cht.get(a[i].r + 1);
      cnt = res.second + 1;
      cur = sqr(a[i].r + 1) + res.first + lam;
    }
    return {cur, cnt};
  };
  i64 left = 0;
  i64 right = (i64) 1e13;
  while (left + 1 != right) {
    auto middle = (left + right) / 2;
    auto[score, nsqs] = calc(middle);
    if (nsqs > mx) {
      left = middle;
    } else {
      right = middle;
    }
  }
  auto get_cost = [](auto p, auto lam) {
    return p.first - p.second * lam;
  };
  auto f_right = calc(right);
  if (f_right.second == mx) {
    return get_cost(f_right, right);
  }
  auto f_left = calc(left);
  if (f_left.second == mx) {
    return get_cost(f_left, left);
  }

  auto k = static_cast<long double>(get_cost(f_left, left) - get_cost(f_right,
          right)) /
          (f_left.second - f_right.second);
  auto b = get_cost(f_left, left) - k * f_left.second;
  return (i64) roundl(k * mx + b);
}

//i64 take_photos_ac(int n, int, int mx, vector<int> r, vector<int> c) {
//  struct cell {
//    int r, c;
//
//    cell(int r_, int c_) : r(r_), c(c_) {}
//  };
//  vector<cell> a;
//  {
//    for (int i = 0; i < n; ++i) {
//      if (r[i] < c[i]) {
//        swap(r[i], c[i]);
//      }
//    }
//    vector<int> p(n);
//    iota(p.begin(), p.end(), 0);
//    sort(p.begin(), p.end(), [&](int i, int j) {
//      if (r[i] != r[j]) {
//        return r[i] < r[j];
//      }
//      return c[i] > c[j];
//    });
//    for (int i = 0; i < n; ++i) {
//      while (!a.empty() && a.back().c >= c[p[i]]) {
//        a.pop_back();
//      }
//      a.emplace_back(r[p[i]], c[p[i]]);
//    }
//  }
//  n = (int) a.size();
//  mx = min(mx, n);
//  i64 const INF = (i64) 1e18;
//  vector<vector<i64>> dp(n + 1, vector<i64>(mx + 1, INF));
//  fill(dp[0].begin(), dp[0].end(), 0);
//  auto relax = [&](i64& x, i64 y) {
//    if (y < x) {
//      x = y;
//    }
//  };
//  auto sqr = [](i64 x) {
//    return x * x;
//  };
//  for (int k = 1; k <= mx; ++k) {
//    hull<i64> cht;
//    for (int i = 0; i < n; ++i) {
//      //  dp[i + 1][k]
//      auto ci = !i ? 0 : sqr(
//              max<i64>(0, a[i - 1].r - a[i].c + 1));
//      cht.add_line({-2 * a[i].c, sqr(a[i].c) + dp[i][k - 1] - ci}, 0);
//      dp[i + 1][k] = sqr(a[i].r + 1) + cht.get(a[i].r + 1).first;
//    }
//  }
//  return dp.back().back();
//}

//#define STRESS
//
//int main() {
//#ifdef STRESS
//  mt19937 rng(566);
//  auto rnd = [&](auto from, auto to) {
//    return uniform_int_distribution<decltype(from)>(from, to)(rng);
//  };
//  int const N = 30;
//  int const M = 30;
//  for (int it = 0; ; ++it) {
//    cerr << it << '\n';
//    if (it == 4) {
//      cerr << "elegiggle\n";
//    }
//    int n = rnd(1, N);
//    int m = rnd(1, M);
//    vector<int> r(n);
//    vector<int> c(n);
//    for (int i = 0; i < n; ++i) {
//      r[i] = rnd(0, m - 1);
//      c[i] = r[i];
//    }
//    int k = rnd(1, n);
//    auto ac = take_photos_ac(n, m, k, r, c);
//    auto wa = take_photos(n, m, k, r, c);
//    if (ac != wa) {
//      cout << ac << ' ' << wa << endl;
//      cout << n << ' ' << m << ' ' << k << endl;
//      for (int i = 0; i < n; ++i) {
//        cout << r[i] << ' ' << c[i] << endl;
//      }
//      return 0;
//    }
//    cout << "passed " << ac << endl;
//  }
//#else
//  vector<int> r{2, 3, 4, 5};
////  vector<int> r{1, 2, 3, 4};
//  auto c = r;
//  int m = 6;
//  int k = 3;
//  cout << take_photos((int) r.size(), m, k, r, c) << '\n';
//#endif
//}
//
///*
// 6 8
//  4 6 3
//  2 2
//  4 4
//  3 3
//  5 5
// */

Compilation message

aliens.cpp: In function 'i64 take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:113:9: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
     auto[score, nsqs] = calc(middle);
         ^
aliens.cpp:113:21: warning: unused variable 'score' [-Wunused-variable]
     auto[score, nsqs] = calc(middle);
                     ^

Subtask #1
4.0 / 4.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Correct answer: answer = 4
2 Correct 2 ms 376 KB Correct answer: answer = 4
3 Correct 2 ms 256 KB Correct answer: answer = 4
4 Correct 2 ms 376 KB Correct answer: answer = 12
5 Correct 2 ms 376 KB Correct answer: answer = 52
6 Correct 2 ms 256 KB Correct answer: answer = 210
7 Correct 2 ms 376 KB Correct answer: answer = 88
8 Correct 2 ms 380 KB Correct answer: answer = 7696
9 Correct 2 ms 376 KB Correct answer: answer = 1
10 Correct 2 ms 376 KB Correct answer: answer = 2374
11 Correct 2 ms 376 KB Correct answer: answer = 9502
12 Correct 2 ms 376 KB Correct answer: answer = 49
13 Correct 2 ms 256 KB Correct answer: answer = 151
14 Correct 2 ms 256 KB Correct answer: answer = 7550
15 Correct 2 ms 256 KB Correct answer: answer = 7220
16 Correct 2 ms 376 KB Correct answer: answer = 7550
17 Correct 2 ms 376 KB Correct answer: answer = 10000
18 Correct 2 ms 256 KB Correct answer: answer = 10000
19 Correct 2 ms 376 KB Correct answer: answer = 624
20 Correct 2 ms 256 KB Correct answer: answer = 10000
21 Correct 2 ms 376 KB Correct answer: answer = 1
22 Correct 2 ms 376 KB Correct answer: answer = 4
23 Correct 2 ms 256 KB Correct answer: answer = 1
24 Correct 2 ms 256 KB Correct answer: answer = 5
25 Correct 2 ms 256 KB Correct answer: answer = 41
26 Correct 2 ms 376 KB Correct answer: answer = 71923
27 Correct 2 ms 376 KB Correct answer: answer = 77137
28 Correct 3 ms 376 KB Correct answer: answer = 764
29 Correct 3 ms 376 KB Correct answer: answer = 250000
30 Correct 3 ms 376 KB Correct answer: answer = 500
31 Correct 2 ms 376 KB Correct answer: answer = 32
32 Correct 3 ms 376 KB Correct answer: answer = 130050
33 Correct 3 ms 376 KB Correct answer: answer = 5110
34 Correct 2 ms 376 KB Correct answer: answer = 2626
35 Correct 2 ms 376 KB Correct answer: answer = 796
36 Correct 3 ms 376 KB Correct answer: answer = 7580
37 Correct 3 ms 376 KB Correct answer: answer = 1904
38 Correct 3 ms 376 KB Correct answer: answer = 996004
39 Correct 3 ms 376 KB Correct answer: answer = 38817
40 Correct 3 ms 376 KB Correct answer: answer = 4096
41 Correct 2 ms 252 KB Correct answer: answer = 1
42 Correct 2 ms 252 KB Correct answer: answer = 1
43 Correct 3 ms 376 KB Correct answer: answer = 2040
44 Correct 2 ms 256 KB Correct answer: answer = 2
45 Correct 2 ms 376 KB Correct answer: answer = 4
46 Correct 2 ms 256 KB Correct answer: answer = 9
47 Correct 2 ms 376 KB Correct answer: answer = 9
48 Correct 2 ms 256 KB Correct answer: answer = 21
49 Correct 2 ms 380 KB Correct answer: answer = 71
50 Correct 2 ms 256 KB Correct answer: answer = 77
51 Correct 2 ms 376 KB Correct answer: answer = 400
52 Correct 2 ms 524 KB Correct answer: answer = 996004
53 Correct 2 ms 376 KB Correct answer: answer = 997310
54 Correct 2 ms 376 KB Correct answer: answer = 990781
55 Correct 2 ms 376 KB Correct answer: answer = 996545
56 Correct 2 ms 256 KB Correct answer: answer = 484
57 Correct 2 ms 376 KB Correct answer: answer = 484
58 Correct 3 ms 372 KB Correct answer: answer = 63501
59 Correct 3 ms 376 KB Correct answer: answer = 323501
60 Correct 3 ms 376 KB Correct answer: answer = 752500
61 Correct 3 ms 376 KB Correct answer: answer = 761480
62 Correct 3 ms 376 KB Correct answer: answer = 758932
63 Correct 2 ms 376 KB Correct answer: answer = 1000000
64 Correct 3 ms 376 KB Correct answer: answer = 750500
65 Correct 2 ms 252 KB Correct answer: answer = 1000000
66 Correct 2 ms 376 KB Correct answer: answer = 250000
67 Correct 2 ms 376 KB Correct answer: answer = 250000
68 Correct 2 ms 256 KB Correct answer: answer = 1000000
69 Correct 2 ms 256 KB Correct answer: answer = 994009
70 Correct 3 ms 256 KB Correct answer: answer = 59315
71 Correct 3 ms 376 KB Correct answer: answer = 25454
72 Correct 3 ms 376 KB Correct answer: answer = 1504
73 Correct 3 ms 376 KB Correct answer: answer = 37486
74 Correct 3 ms 376 KB Correct answer: answer = 4284
75 Correct 2 ms 376 KB Correct answer: answer = 158008
76 Correct 2 ms 376 KB Correct answer: answer = 51860
77 Correct 2 ms 376 KB Correct answer: answer = 12985
78 Correct 4 ms 376 KB Correct answer: answer = 997864126212
79 Correct 4 ms 376 KB Correct answer: answer = 998608411647
80 Correct 4 ms 504 KB Correct answer: answer = 995265560477
81 Correct 10 ms 724 KB Correct answer: answer = 10125000
82 Correct 13 ms 956 KB Correct answer: answer = 2291668
83 Correct 7 ms 688 KB Correct answer: answer = 42388
84 Correct 7 ms 716 KB Correct answer: answer = 10318
85 Correct 7 ms 672 KB Correct answer: answer = 3416
86 Correct 11 ms 504 KB Correct answer: answer = 331708193881
87 Correct 12 ms 632 KB Correct answer: answer = 2861193756
88 Correct 15 ms 960 KB Correct answer: answer = 114646930
89 Correct 13 ms 996 KB Correct answer: answer = 9280921
90 Correct 14 ms 1044 KB Correct answer: answer = 999984053400
91 Correct 13 ms 760 KB Correct answer: answer = 750935949134
92 Correct 3 ms 504 KB Correct answer: answer = 1000000000000
93 Correct 4 ms 504 KB Correct answer: answer = 998762383161
94 Correct 11 ms 504 KB Correct answer: answer = 23017412908
95 Correct 4 ms 504 KB Correct answer: answer = 728143410622
96 Correct 3 ms 380 KB Correct answer: answer = 2
97 Correct 13 ms 924 KB Correct answer: answer = 1824916
98 Correct 10 ms 780 KB Correct answer: answer = 10680029
99 Correct 13 ms 952 KB Correct answer: answer = 18351700
100 Correct 10 ms 772 KB Correct answer: answer = 16040026
101 Correct 4 ms 504 KB Correct answer: answer = 253968628325
102 Correct 7 ms 668 KB Correct answer: answer = 10267
103 Correct 15 ms 1028 KB Correct answer: answer = 2582408
104 Correct 4 ms 476 KB Correct answer: answer = 78024964781
105 Correct 4 ms 504 KB Correct answer: answer = 9866346457
106 Correct 4 ms 508 KB Correct answer: answer = 3327720949
107 Correct 4 ms 632 KB Correct answer: answer = 86064128360
108 Correct 5 ms 504 KB Correct answer: answer = 12698259150
109 Correct 12 ms 972 KB Correct answer: answer = 1185259288

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Correct answer: answer = 4
2 Correct 2 ms 376 KB Correct answer: answer = 4
3 Correct 2 ms 256 KB Correct answer: answer = 4
4 Correct 2 ms 376 KB Correct answer: answer = 12
5 Correct 2 ms 376 KB Correct answer: answer = 52
6 Correct 2 ms 256 KB Correct answer: answer = 210
7 Correct 2 ms 376 KB Correct answer: answer = 88
8 Correct 2 ms 380 KB Correct answer: answer = 7696
9 Correct 2 ms 376 KB Correct answer: answer = 1
10 Correct 2 ms 376 KB Correct answer: answer = 2374
11 Correct 2 ms 376 KB Correct answer: answer = 9502
12 Correct 2 ms 376 KB Correct answer: answer = 49
13 Correct 2 ms 256 KB Correct answer: answer = 151
14 Correct 2 ms 256 KB Correct answer: answer = 7550
15 Correct 2 ms 256 KB Correct answer: answer = 7220
16 Correct 2 ms 376 KB Correct answer: answer = 7550
17 Correct 2 ms 376 KB Correct answer: answer = 10000
18 Correct 2 ms 256 KB Correct answer: answer = 10000
19 Correct 2 ms 376 KB Correct answer: answer = 624
20 Correct 2 ms 256 KB Correct answer: answer = 10000
21 Correct 2 ms 376 KB Correct answer: answer = 1
22 Correct 2 ms 376 KB Correct answer: answer = 4
23 Correct 2 ms 256 KB Correct answer: answer = 1
24 Correct 2 ms 256 KB Correct answer: answer = 5
25 Correct 2 ms 256 KB Correct answer: answer = 41
26 Correct 2 ms 376 KB Correct answer: answer = 71923
27 Correct 2 ms 376 KB Correct answer: answer = 77137
28 Correct 3 ms 376 KB Correct answer: answer = 764
29 Correct 3 ms 376 KB Correct answer: answer = 250000
30 Correct 3 ms 376 KB Correct answer: answer = 500
31 Correct 2 ms 376 KB Correct answer: answer = 32
32 Correct 3 ms 376 KB Correct answer: answer = 130050
33 Correct 3 ms 376 KB Correct answer: answer = 5110
34 Correct 2 ms 376 KB Correct answer: answer = 2626
35 Correct 2 ms 376 KB Correct answer: answer = 796
36 Correct 3 ms 376 KB Correct answer: answer = 7580
37 Correct 3 ms 376 KB Correct answer: answer = 1904
38 Correct 3 ms 376 KB Correct answer: answer = 996004
39 Correct 3 ms 376 KB Correct answer: answer = 38817
40 Correct 3 ms 376 KB Correct answer: answer = 4096
41 Correct 2 ms 252 KB Correct answer: answer = 1
42 Correct 2 ms 252 KB Correct answer: answer = 1
43 Correct 3 ms 376 KB Correct answer: answer = 2040
44 Correct 2 ms 256 KB Correct answer: answer = 2
45 Correct 2 ms 376 KB Correct answer: answer = 4
46 Correct 2 ms 256 KB Correct answer: answer = 9
47 Correct 2 ms 376 KB Correct answer: answer = 9
48 Correct 2 ms 256 KB Correct answer: answer = 21
49 Correct 2 ms 380 KB Correct answer: answer = 71
50 Correct 2 ms 256 KB Correct answer: answer = 77
51 Correct 2 ms 376 KB Correct answer: answer = 400
52 Correct 2 ms 524 KB Correct answer: answer = 996004
53 Correct 2 ms 376 KB Correct answer: answer = 997310
54 Correct 2 ms 376 KB Correct answer: answer = 990781
55 Correct 2 ms 376 KB Correct answer: answer = 996545
56 Correct 2 ms 256 KB Correct answer: answer = 484
57 Correct 2 ms 376 KB Correct answer: answer = 484
58 Correct 3 ms 372 KB Correct answer: answer = 63501
59 Correct 3 ms 376 KB Correct answer: answer = 323501
60 Correct 3 ms 376 KB Correct answer: answer = 752500
61 Correct 3 ms 376 KB Correct answer: answer = 761480
62 Correct 3 ms 376 KB Correct answer: answer = 758932
63 Correct 2 ms 376 KB Correct answer: answer = 1000000
64 Correct 3 ms 376 KB Correct answer: answer = 750500
65 Correct 2 ms 252 KB Correct answer: answer = 1000000
66 Correct 2 ms 376 KB Correct answer: answer = 250000
67 Correct 2 ms 376 KB Correct answer: answer = 250000
68 Correct 2 ms 256 KB Correct answer: answer = 1000000
69 Correct 2 ms 256 KB Correct answer: answer = 994009
70 Correct 3 ms 256 KB Correct answer: answer = 59315
71 Correct 3 ms 376 KB Correct answer: answer = 25454
72 Correct 3 ms 376 KB Correct answer: answer = 1504
73 Correct 3 ms 376 KB Correct answer: answer = 37486
74 Correct 3 ms 376 KB Correct answer: answer = 4284
75 Correct 2 ms 376 KB Correct answer: answer = 158008
76 Correct 2 ms 376 KB Correct answer: answer = 51860
77 Correct 2 ms 376 KB Correct answer: answer = 12985
78 Correct 4 ms 376 KB Correct answer: answer = 997864126212
79 Correct 4 ms 376 KB Correct answer: answer = 998608411647
80 Correct 4 ms 504 KB Correct answer: answer = 995265560477
81 Correct 10 ms 724 KB Correct answer: answer = 10125000
82 Correct 13 ms 956 KB Correct answer: answer = 2291668
83 Correct 7 ms 688 KB Correct answer: answer = 42388
84 Correct 7 ms 716 KB Correct answer: answer = 10318
85 Correct 7 ms 672 KB Correct answer: answer = 3416
86 Correct 11 ms 504 KB Correct answer: answer = 331708193881
87 Correct 12 ms 632 KB Correct answer: answer = 2861193756
88 Correct 15 ms 960 KB Correct answer: answer = 114646930
89 Correct 13 ms 996 KB Correct answer: answer = 9280921
90 Correct 14 ms 1044 KB Correct answer: answer = 999984053400
91 Correct 13 ms 760 KB Correct answer: answer = 750935949134
92 Correct 3 ms 504 KB Correct answer: answer = 1000000000000
93 Correct 4 ms 504 KB Correct answer: answer = 998762383161
94 Correct 11 ms 504 KB Correct answer: answer = 23017412908
95 Correct 4 ms 504 KB Correct answer: answer = 728143410622
96 Correct 3 ms 380 KB Correct answer: answer = 2
97 Correct 13 ms 924 KB Correct answer: answer = 1824916
98 Correct 10 ms 780 KB Correct answer: answer = 10680029
99 Correct 13 ms 952 KB Correct answer: answer = 18351700
100 Correct 10 ms 772 KB Correct answer: answer = 16040026
101 Correct 4 ms 504 KB Correct answer: answer = 253968628325
102 Correct 7 ms 668 KB Correct answer: answer = 10267
103 Correct 15 ms 1028 KB Correct answer: answer = 2582408
104 Correct 4 ms 476 KB Correct answer: answer = 78024964781
105 Correct 4 ms 504 KB Correct answer: answer = 9866346457
106 Correct 4 ms 508 KB Correct answer: answer = 3327720949
107 Correct 4 ms 632 KB Correct answer: answer = 86064128360
108 Correct 5 ms 504 KB Correct answer: answer = 12698259150
109 Correct 12 ms 972 KB Correct answer: answer = 1185259288
110 Correct 23 ms 1916 KB Correct answer: answer = 999889968863
111 Correct 24 ms 1912 KB Correct answer: answer = 999861384931
112 Correct 24 ms 2060 KB Correct answer: answer = 999811809929
113 Correct 23 ms 1912 KB Correct answer: answer = 999869756441
114 Correct 151 ms 5412 KB Correct answer: answer = 1700000000
115 Correct 219 ms 8788 KB Correct answer: answer = 131666670
116 Correct 80 ms 2536 KB Correct answer: answer = 89478486
117 Correct 36 ms 2920 KB Correct answer: answer = 4971040
118 Correct 36 ms 2916 KB Correct answer: answer = 2711494
119 Correct 257 ms 9212 KB Correct answer: answer = 25252530
120 Correct 236 ms 9268 KB Correct answer: answer = 62500000
121 Correct 115 ms 2676 KB Correct answer: answer = 333175097780
122 Correct 120 ms 2700 KB Correct answer: answer = 33121180179
123 Correct 117 ms 2676 KB Correct answer: answer = 9802314015
124 Correct 221 ms 9420 KB Correct answer: answer = 32567551
125 Correct 246 ms 9356 KB Correct answer: answer = 997525000000
126 Correct 113 ms 2548 KB Correct answer: answer = 752723538884
127 Correct 15 ms 1912 KB Correct answer: answer = 1000000000000
128 Correct 23 ms 1912 KB Correct answer: answer = 999978000121
129 Correct 24 ms 1912 KB Correct answer: answer = 745986144735
130 Correct 12 ms 1532 KB Correct answer: answer = 2
131 Correct 209 ms 8636 KB Correct answer: answer = 277966670
132 Correct 148 ms 5732 KB Correct answer: answer = 2500900082
133 Correct 33 ms 2024 KB Correct answer: answer = 301248349636
134 Correct 83 ms 3056 KB Correct answer: answer = 14118891
135 Correct 23 ms 1900 KB Correct answer: answer = 14384977265
136 Correct 24 ms 1912 KB Correct answer: answer = 3681368330
137 Correct 25 ms 2040 KB Correct answer: answer = 2720316816

Subtask #6
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Correct answer: answer = 4
2 Correct 2 ms 376 KB Correct answer: answer = 4
3 Correct 2 ms 256 KB Correct answer: answer = 4
4 Correct 2 ms 376 KB Correct answer: answer = 12
5 Correct 2 ms 376 KB Correct answer: answer = 52
6 Correct 2 ms 256 KB Correct answer: answer = 210
7 Correct 2 ms 376 KB Correct answer: answer = 88
8 Correct 2 ms 380 KB Correct answer: answer = 7696
9 Correct 2 ms 376 KB Correct answer: answer = 1
10 Correct 2 ms 376 KB Correct answer: answer = 2374
11 Correct 2 ms 376 KB Correct answer: answer = 9502
12 Correct 2 ms 376 KB Correct answer: answer = 49
13 Correct 2 ms 256 KB Correct answer: answer = 151
14 Correct 2 ms 256 KB Correct answer: answer = 7550
15 Correct 2 ms 256 KB Correct answer: answer = 7220
16 Correct 2 ms 376 KB Correct answer: answer = 7550
17 Correct 2 ms 376 KB Correct answer: answer = 10000
18 Correct 2 ms 256 KB Correct answer: answer = 10000
19 Correct 2 ms 376 KB Correct answer: answer = 624
20 Correct 2 ms 256 KB Correct answer: answer = 10000
21 Correct 2 ms 376 KB Correct answer: answer = 1
22 Correct 2 ms 376 KB Correct answer: answer = 4
23 Correct 2 ms 256 KB Correct answer: answer = 1
24 Correct 2 ms 256 KB Correct answer: answer = 5
25 Correct 2 ms 256 KB Correct answer: answer = 41
26 Correct 2 ms 376 KB Correct answer: answer = 71923
27 Correct 2 ms 376 KB Correct answer: answer = 77137
28 Correct 3 ms 376 KB Correct answer: answer = 764
29 Correct 3 ms 376 KB Correct answer: answer = 250000
30 Correct 3 ms 376 KB Correct answer: answer = 500
31 Correct 2 ms 376 KB Correct answer: answer = 32
32 Correct 3 ms 376 KB Correct answer: answer = 130050
33 Correct 3 ms 376 KB Correct answer: answer = 5110
34 Correct 2 ms 376 KB Correct answer: answer = 2626
35 Correct 2 ms 376 KB Correct answer: answer = 796
36 Correct 3 ms 376 KB Correct answer: answer = 7580
37 Correct 3 ms 376 KB Correct answer: answer = 1904
38 Correct 3 ms 376 KB Correct answer: answer = 996004
39 Correct 3 ms 376 KB Correct answer: answer = 38817
40 Correct 3 ms 376 KB Correct answer: answer = 4096
41 Correct 2 ms 252 KB Correct answer: answer = 1
42 Correct 2 ms 252 KB Correct answer: answer = 1
43 Correct 3 ms 376 KB Correct answer: answer = 2040
44 Correct 2 ms 256 KB Correct answer: answer = 2
45 Correct 2 ms 376 KB Correct answer: answer = 4
46 Correct 2 ms 256 KB Correct answer: answer = 9
47 Correct 2 ms 376 KB Correct answer: answer = 9
48 Correct 2 ms 256 KB Correct answer: answer = 21
49 Correct 2 ms 380 KB Correct answer: answer = 71
50 Correct 2 ms 256 KB Correct answer: answer = 77
51 Correct 2 ms 376 KB Correct answer: answer = 400
52 Correct 2 ms 524 KB Correct answer: answer = 996004
53 Correct 2 ms 376 KB Correct answer: answer = 997310
54 Correct 2 ms 376 KB Correct answer: answer = 990781
55 Correct 2 ms 376 KB Correct answer: answer = 996545
56 Correct 2 ms 256 KB Correct answer: answer = 484
57 Correct 2 ms 376 KB Correct answer: answer = 484
58 Correct 3 ms 372 KB Correct answer: answer = 63501
59 Correct 3 ms 376 KB Correct answer: answer = 323501
60 Correct 3 ms 376 KB Correct answer: answer = 752500
61 Correct 3 ms 376 KB Correct answer: answer = 761480
62 Correct 3 ms 376 KB Correct answer: answer = 758932
63 Correct 2 ms 376 KB Correct answer: answer = 1000000
64 Correct 3 ms 376 KB Correct answer: answer = 750500
65 Correct 2 ms 252 KB Correct answer: answer = 1000000
66 Correct 2 ms 376 KB Correct answer: answer = 250000
67 Correct 2 ms 376 KB Correct answer: answer = 250000
68 Correct 2 ms 256 KB Correct answer: answer = 1000000
69 Correct 2 ms 256 KB Correct answer: answer = 994009
70 Correct 3 ms 256 KB Correct answer: answer = 59315
71 Correct 3 ms 376 KB Correct answer: answer = 25454
72 Correct 3 ms 376 KB Correct answer: answer = 1504
73 Correct 3 ms 376 KB Correct answer: answer = 37486
74 Correct 3 ms 376 KB Correct answer: answer = 4284
75 Correct 2 ms 376 KB Correct answer: answer = 158008
76 Correct 2 ms 376 KB Correct answer: answer = 51860
77 Correct 2 ms 376 KB Correct answer: answer = 12985
78 Correct 4 ms 376 KB Correct answer: answer = 997864126212
79 Correct 4 ms 376 KB Correct answer: answer = 998608411647
80 Correct 4 ms 504 KB Correct answer: answer = 995265560477
81 Correct 10 ms 724 KB Correct answer: answer = 10125000
82 Correct 13 ms 956 KB Correct answer: answer = 2291668
83 Correct 7 ms 688 KB Correct answer: answer = 42388
84 Correct 7 ms 716 KB Correct answer: answer = 10318
85 Correct 7 ms 672 KB Correct answer: answer = 3416
86 Correct 11 ms 504 KB Correct answer: answer = 331708193881
87 Correct 12 ms 632 KB Correct answer: answer = 2861193756
88 Correct 15 ms 960 KB Correct answer: answer = 114646930
89 Correct 13 ms 996 KB Correct answer: answer = 9280921
90 Correct 14 ms 1044 KB Correct answer: answer = 999984053400
91 Correct 13 ms 760 KB Correct answer: answer = 750935949134
92 Correct 3 ms 504 KB Correct answer: answer = 1000000000000
93 Correct 4 ms 504 KB Correct answer: answer = 998762383161
94 Correct 11 ms 504 KB Correct answer: answer = 23017412908
95 Correct 4 ms 504 KB Correct answer: answer = 728143410622
96 Correct 3 ms 380 KB Correct answer: answer = 2
97 Correct 13 ms 924 KB Correct answer: answer = 1824916
98 Correct 10 ms 780 KB Correct answer: answer = 10680029
99 Correct 13 ms 952 KB Correct answer: answer = 18351700
100 Correct 10 ms 772 KB Correct answer: answer = 16040026
101 Correct 4 ms 504 KB Correct answer: answer = 253968628325
102 Correct 7 ms 668 KB Correct answer: answer = 10267
103 Correct 15 ms 1028 KB Correct answer: answer = 2582408
104 Correct 4 ms 476 KB Correct answer: answer = 78024964781
105 Correct 4 ms 504 KB Correct answer: answer = 9866346457
106 Correct 4 ms 508 KB Correct answer: answer = 3327720949
107 Correct 4 ms 632 KB Correct answer: answer = 86064128360
108 Correct 5 ms 504 KB Correct answer: answer = 12698259150
109 Correct 12 ms 972 KB Correct answer: answer = 1185259288
110 Correct 23 ms 1916 KB Correct answer: answer = 999889968863
111 Correct 24 ms 1912 KB Correct answer: answer = 999861384931
112 Correct 24 ms 2060 KB Correct answer: answer = 999811809929
113 Correct 23 ms 1912 KB Correct answer: answer = 999869756441
114 Correct 151 ms 5412 KB Correct answer: answer = 1700000000
115 Correct 219 ms 8788 KB Correct answer: answer = 131666670
116 Correct 80 ms 2536 KB Correct answer: answer = 89478486
117 Correct 36 ms 2920 KB Correct answer: answer = 4971040
118 Correct 36 ms 2916 KB Correct answer: answer = 2711494
119 Correct 257 ms 9212 KB Correct answer: answer = 25252530
120 Correct 236 ms 9268 KB Correct answer: answer = 62500000
121 Correct 115 ms 2676 KB Correct answer: answer = 333175097780
122 Correct 120 ms 2700 KB Correct answer: answer = 33121180179
123 Correct 117 ms 2676 KB Correct answer: answer = 9802314015
124 Correct 221 ms 9420 KB Correct answer: answer = 32567551
125 Correct 246 ms 9356 KB Correct answer: answer = 997525000000
126 Correct 113 ms 2548 KB Correct answer: answer = 752723538884
127 Correct 15 ms 1912 KB Correct answer: answer = 1000000000000
128 Correct 23 ms 1912 KB Correct answer: answer = 999978000121
129 Correct 24 ms 1912 KB Correct answer: answer = 745986144735
130 Correct 12 ms 1532 KB Correct answer: answer = 2
131 Correct 209 ms 8636 KB Correct answer: answer = 277966670
132 Correct 148 ms 5732 KB Correct answer: answer = 2500900082
133 Correct 33 ms 2024 KB Correct answer: answer = 301248349636
134 Correct 83 ms 3056 KB Correct answer: answer = 14118891
135 Correct 23 ms 1900 KB Correct answer: answer = 14384977265
136 Correct 24 ms 1912 KB Correct answer: answer = 3681368330
137 Correct 25 ms 2040 KB Correct answer: answer = 2720316816
138 Correct 47 ms 3688 KB Correct answer: answer = 999976000144
139 Correct 47 ms 3704 KB Correct answer: answer = 999856102410
140 Correct 47 ms 3708 KB Correct answer: answer = 999958401531
141 Correct 47 ms 3704 KB Correct answer: answer = 999769649944
142 Correct 49 ms 3704 KB Correct answer: answer = 999874525918
143 Correct 327 ms 10836 KB Correct answer: answer = 6050000000
144 Correct 536 ms 16440 KB Correct answer: answer = 1112500000
145 Correct 204 ms 8940 KB Correct answer: answer = 4294967296
146 Correct 276 ms 10576 KB Correct answer: answer = 87652406
147 Correct 313 ms 10828 KB Correct answer: answer = 6297664
148 Correct 288 ms 10888 KB Correct answer: answer = 196612
149 Correct 552 ms 18288 KB Correct answer: answer = 15015100
150 Correct 522 ms 18272 KB Correct answer: answer = 25000000
151 Correct 227 ms 4796 KB Correct answer: answer = 333230209550
152 Correct 241 ms 4952 KB Correct answer: answer = 917123769
153 Correct 341 ms 18200 KB Correct answer: answer = 95162
154 Correct 543 ms 18052 KB Correct answer: answer = 382616191
155 Correct 520 ms 18360 KB Correct answer: answer = 990033333400
156 Correct 491 ms 18468 KB Correct answer: answer = 990000100000
157 Correct 257 ms 16236 KB Correct answer: answer = 749998188180
158 Correct 29 ms 3576 KB Correct answer: answer = 1000000000000
159 Correct 44 ms 3576 KB Correct answer: answer = 999988000036
160 Correct 47 ms 3704 KB Correct answer: answer = 744929274393
161 Correct 23 ms 2680 KB Correct answer: answer = 2
162 Correct 482 ms 18388 KB Correct answer: answer = 1300024
163 Correct 335 ms 11508 KB Correct answer: answer = 5000700010
164 Correct 66 ms 3704 KB Correct answer: answer = 354997100800
165 Correct 190 ms 8472 KB Correct answer: answer = 257000
166 Correct 262 ms 9412 KB Correct answer: answer = 3765323
167 Correct 254 ms 9500 KB Correct answer: answer = 1525903
168 Correct 46 ms 3576 KB Correct answer: answer = 67618137730
169 Correct 47 ms 3576 KB Correct answer: answer = 12656680171
170 Correct 52 ms 3704 KB Correct answer: answer = 579831736
171 Correct 117 ms 5496 KB Correct answer: answer = 23605611
172 Correct 51 ms 3824 KB Correct answer: answer = 7052481200
173 Correct 74 ms 5284 KB Correct answer: answer = 1314039500
174 Correct 94 ms 6700 KB Correct answer: answer = 302484000
175 Correct 175 ms 7152 KB Correct answer: answer = 52348480