oj.uz

Submission #529917

# Submission time Handle Problem Language Result Execution time Memory
529917 2022-02-24T03:17:40 Z msg555 Aliens (IOI16_aliens) C++14
100 / 100
 398 ms 11968 KB 
#include "aliens.h"

#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
#include <cassert>

using namespace std;

long long squared(int x) {
  return 1ll * x * x;
}

template<typename T>
struct line_elem {
  T a;
  T b;
  T x_start;
  bool point_query;

  line_elem() : a(0), b(0), x_start(0), point_query(false) {}
  line_elem(T x) : a(0), b(0), x_start(x), point_query(true) {}
  line_elem(T a, T b, T x_start = 0) : a(a), b(b), x_start(x_start), point_query(false) {}

  T get(T x) const {
    return a * x + b;
  }

  bool operator<(const line_elem& rhs) const {
    if (point_query || rhs.point_query) {
      return x_start < rhs.x_start;
    }
    return make_pair(a, b) < make_pair(rhs.a, rhs.b);
  }
};

template<typename T>
struct rolling_line_hull {
  /*
  Implements a max hull, get the max ax+b for all inserted lines. 

  This requires the a's to be non-decreasing between inserts and for calls
  to get(x) to be on non-decreasing x. This removes the log(N) factor present
  in line_hull and gives amortized constant time insert/query.
   */
  rolling_line_hull() : query_index(0) {}

  void insert(T a, T b) {
    /* Insert line ax+b */
    assert(lns.empty() || lns.back().a <= a);
    if (!lns.empty() && lns.back().a == a) {
      if (b <= lns.back().b) {
        return;
      }
      lns.resize(lns.size() - 1);
    }

    auto ln = line_elem<T>(a, b);
    if (lns.empty()) {
      ln.x_start = numeric_limits<T>::min();
      lns.push_back(ln);
      return;
    }

    size_t sz = lns.size();
    ln.x_start = cross_x(lns[sz - 1], ln);
    while (sz > 1) {
      if (lns[sz - 1].x_start < ln.x_start) {
        break;
      }
      --sz;
      ln.x_start = cross_x(lns[sz - 1], ln);
    }
    lns.resize(sz);

    ln.x_start = cross_x(lns.back(), ln);
    lns.push_back(ln);
    query_index = min(query_index, lns.size() - 1);
  }

  T get(T x) {
    while (query_index + 1 < lns.size() && x >= lns[query_index + 1].x_start) {
      ++query_index;
    }
    return lns[query_index].get(x);
  }

private:
  T cross_x(const line_elem<T>& X, const line_elem<T>& Y) {
    /* Returns the first x >= to when the lines intersect */
    T da = X.a - Y.a;
    T db = Y.b - X.b;
    assert(da != 0);
    if (da < 0) {
      da = -da;
      db = -db;
    }
    if (db < 0) {
      return db / da;
    }
    return (db + da - 1) / da;
  }

  size_t query_index;
  vector<line_elem<T> > lns;
};

const size_t MAXN = 100010;

pair<int, int> A[MAXN];
long long ADJ[MAXN];

long long sample(int N, int K, long long C) {
  rolling_line_hull<long long> hl;
  long long val = 0;
  for (int i = 0; ; i++) {
    val = 0;
    if (i) {
      long long x = A[i - 1].first;
      val = -hl.get(x) + squared(x) + C;
    }
    if (i == N) break;

    long long sadd = 1 + A[i].second - A[i].first;
    long long b = 2 * sadd;
    long long c = squared(sadd) + val - ADJ[i];
    hl.insert(-b, -c);
  }

  return val - K * C;
}

long long take_photos(int N, int M, int K, vector<int> R, vector<int> C) {
/*
  N = 100000;
  M = 100001;
  K = 50000;
  R.clear();
  C.clear();
  for (int i = 0; i < N; i++) {
    R.push_back(i);
    C.push_back(i + 1);
  }
*/

  for (int i = 0; i < N; i++) {
    int ri = R[i];
    int ci = C[i];
    if (ri > ci) swap(ri, ci);
    A[i] = make_pair(ci, ci - ri);
  }
  sort(A, A + N);

  int j = 0;
  for (int i = 0; i < N; i++) {
    while (j > 0 && A[i].second - A[i].first >= A[j - 1].second - A[j - 1].first) {
      --j;
    }
    A[j++] = A[i];
  }
  N = j;
  K = min(K, N);

  for (int i = 1; i < N; i++) {
    ADJ[i] = squared(max(0, 1 + A[i].second - A[i].first + A[i - 1].first));
  }

  long long lo = 0;
  long long hi = 1 << 16;
  long long md = hi;
  long long mdv = sample(N, K, md);
  while (true) {
    long long v = sample(N, K, 2 * hi);
    if (v <= mdv) {
      hi *= 2;
      break;
    }
    lo = hi;
    hi *= 2;
    md = hi;
    mdv = v;
  }

  while (lo + 4 <= hi) {
    long long nmd;
    if (hi - md < md - lo) {
      nmd = lo + (md - lo) / 2;
    } else {
      nmd = md + (hi - md) / 2;
    }
    long long nmdv = sample(N, K, nmd);

    if (md < nmd) {
      swap(md, nmd);
      swap(mdv, nmdv);
    }

    if (nmdv < mdv) {
      lo = nmd + 1;
    } else {
      hi = md;
      md = nmd;
      mdv = nmdv;
    }
  }

  long long result = numeric_limits<long long>::min();
  for (long long i = lo; i < hi; i++) {
    result = max(result, sample(N, K, i));
  }
  return result;
}

Subtask #1
4.0 / 4.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Correct answer: answer = 4
2 Correct 0 ms 204 KB Correct answer: answer = 4
3 Correct 0 ms 204 KB Correct answer: answer = 4
4 Correct 1 ms 204 KB Correct answer: answer = 12
5 Correct 0 ms 204 KB Correct answer: answer = 52
6 Correct 0 ms 204 KB Correct answer: answer = 210
7 Correct 0 ms 204 KB Correct answer: answer = 88
8 Correct 1 ms 332 KB Correct answer: answer = 7696
9 Correct 0 ms 204 KB Correct answer: answer = 1
10 Correct 0 ms 204 KB Correct answer: answer = 2374
11 Correct 1 ms 204 KB Correct answer: answer = 9502
12 Correct 0 ms 204 KB Correct answer: answer = 49
13 Correct 1 ms 304 KB Correct answer: answer = 151
14 Correct 0 ms 204 KB Correct answer: answer = 7550
15 Correct 1 ms 204 KB Correct answer: answer = 7220
16 Correct 1 ms 296 KB Correct answer: answer = 7550
17 Correct 0 ms 204 KB Correct answer: answer = 10000
18 Correct 1 ms 204 KB Correct answer: answer = 10000
19 Correct 1 ms 204 KB Correct answer: answer = 624
20 Correct 0 ms 204 KB Correct answer: answer = 10000
21 Correct 0 ms 204 KB Correct answer: answer = 1
22 Correct 0 ms 204 KB Correct answer: answer = 4
23 Correct 1 ms 276 KB Correct answer: answer = 1
24 Correct 1 ms 204 KB Correct answer: answer = 5
25 Correct 0 ms 204 KB Correct answer: answer = 41
26 Correct 1 ms 204 KB Correct answer: answer = 71923
27 Correct 1 ms 204 KB Correct answer: answer = 77137
28 Correct 1 ms 332 KB Correct answer: answer = 764
29 Correct 1 ms 332 KB Correct answer: answer = 250000
30 Correct 1 ms 332 KB Correct answer: answer = 500
31 Correct 0 ms 292 KB Correct answer: answer = 32
32 Correct 1 ms 304 KB Correct answer: answer = 130050
33 Correct 1 ms 332 KB Correct answer: answer = 5110
34 Correct 1 ms 204 KB Correct answer: answer = 2626
35 Correct 1 ms 300 KB Correct answer: answer = 796
36 Correct 1 ms 336 KB Correct answer: answer = 7580
37 Correct 1 ms 332 KB Correct answer: answer = 1904
38 Correct 1 ms 204 KB Correct answer: answer = 996004
39 Correct 1 ms 204 KB Correct answer: answer = 38817
40 Correct 1 ms 292 KB Correct answer: answer = 4096
41 Correct 1 ms 204 KB Correct answer: answer = 1
42 Correct 0 ms 204 KB Correct answer: answer = 1
43 Correct 1 ms 332 KB Correct answer: answer = 2040
44 Correct 1 ms 204 KB Correct answer: answer = 2
45 Correct 0 ms 204 KB Correct answer: answer = 4
46 Correct 0 ms 204 KB Correct answer: answer = 9
47 Correct 0 ms 296 KB Correct answer: answer = 9
48 Correct 1 ms 204 KB Correct answer: answer = 21
49 Correct 1 ms 204 KB Correct answer: answer = 71
50 Correct 1 ms 204 KB Correct answer: answer = 77
51 Correct 1 ms 204 KB Correct answer: answer = 400
52 Correct 1 ms 300 KB Correct answer: answer = 996004
53 Correct 1 ms 204 KB Correct answer: answer = 997310
54 Correct 1 ms 204 KB Correct answer: answer = 990781
55 Correct 1 ms 304 KB Correct answer: answer = 996545
56 Correct 1 ms 204 KB Correct answer: answer = 484
57 Correct 1 ms 204 KB Correct answer: answer = 484
58 Correct 1 ms 304 KB Correct answer: answer = 63501
59 Correct 1 ms 332 KB Correct answer: answer = 323501
60 Correct 1 ms 296 KB Correct answer: answer = 752500
61 Correct 1 ms 204 KB Correct answer: answer = 761480
62 Correct 1 ms 204 KB Correct answer: answer = 758932
63 Correct 1 ms 296 KB Correct answer: answer = 1000000
64 Correct 2 ms 332 KB Correct answer: answer = 750500
65 Correct 1 ms 204 KB Correct answer: answer = 1000000
66 Correct 1 ms 204 KB Correct answer: answer = 250000
67 Correct 1 ms 204 KB Correct answer: answer = 250000
68 Correct 1 ms 296 KB Correct answer: answer = 1000000
69 Correct 1 ms 208 KB Correct answer: answer = 994009
70 Correct 1 ms 304 KB Correct answer: answer = 59315
71 Correct 1 ms 300 KB Correct answer: answer = 25454
72 Correct 1 ms 204 KB Correct answer: answer = 1504
73 Correct 1 ms 204 KB Correct answer: answer = 37486
74 Correct 1 ms 320 KB Correct answer: answer = 4284
75 Correct 1 ms 312 KB Correct answer: answer = 158008
76 Correct 1 ms 204 KB Correct answer: answer = 51860
77 Correct 1 ms 204 KB Correct answer: answer = 12985
78 Correct 2 ms 332 KB Correct answer: answer = 997864126212
79 Correct 1 ms 440 KB Correct answer: answer = 998608411647
80 Correct 2 ms 452 KB Correct answer: answer = 995265560477
81 Correct 6 ms 660 KB Correct answer: answer = 10125000
82 Correct 6 ms 680 KB Correct answer: answer = 2291668
83 Correct 2 ms 460 KB Correct answer: answer = 42388
84 Correct 3 ms 460 KB Correct answer: answer = 10318
85 Correct 3 ms 460 KB Correct answer: answer = 3416
86 Correct 14 ms 632 KB Correct answer: answer = 331708193881
87 Correct 8 ms 692 KB Correct answer: answer = 2861193756
88 Correct 7 ms 684 KB Correct answer: answer = 114646930
89 Correct 5 ms 728 KB Correct answer: answer = 9280921
90 Correct 5 ms 728 KB Correct answer: answer = 999984053400
91 Correct 6 ms 588 KB Correct answer: answer = 750935949134
92 Correct 1 ms 436 KB Correct answer: answer = 1000000000000
93 Correct 2 ms 332 KB Correct answer: answer = 998762383161
94 Correct 10 ms 620 KB Correct answer: answer = 23017412908
95 Correct 2 ms 332 KB Correct answer: answer = 728143410622
96 Correct 2 ms 332 KB Correct answer: answer = 2
97 Correct 9 ms 700 KB Correct answer: answer = 1824916
98 Correct 6 ms 564 KB Correct answer: answer = 10680029
99 Correct 8 ms 704 KB Correct answer: answer = 18351700
100 Correct 6 ms 676 KB Correct answer: answer = 16040026
101 Correct 2 ms 436 KB Correct answer: answer = 253968628325
102 Correct 4 ms 460 KB Correct answer: answer = 10267
103 Correct 6 ms 728 KB Correct answer: answer = 2582408
104 Correct 2 ms 332 KB Correct answer: answer = 78024964781
105 Correct 2 ms 332 KB Correct answer: answer = 9866346457
106 Correct 2 ms 460 KB Correct answer: answer = 3327720949
107 Correct 2 ms 440 KB Correct answer: answer = 86064128360
108 Correct 2 ms 460 KB Correct answer: answer = 12698259150
109 Correct 5 ms 704 KB Correct answer: answer = 1185259288

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Correct answer: answer = 4
2 Correct 0 ms 204 KB Correct answer: answer = 4
3 Correct 0 ms 204 KB Correct answer: answer = 4
4 Correct 1 ms 204 KB Correct answer: answer = 12
5 Correct 0 ms 204 KB Correct answer: answer = 52
6 Correct 0 ms 204 KB Correct answer: answer = 210
7 Correct 0 ms 204 KB Correct answer: answer = 88
8 Correct 1 ms 332 KB Correct answer: answer = 7696
9 Correct 0 ms 204 KB Correct answer: answer = 1
10 Correct 0 ms 204 KB Correct answer: answer = 2374
11 Correct 1 ms 204 KB Correct answer: answer = 9502
12 Correct 0 ms 204 KB Correct answer: answer = 49
13 Correct 1 ms 304 KB Correct answer: answer = 151
14 Correct 0 ms 204 KB Correct answer: answer = 7550
15 Correct 1 ms 204 KB Correct answer: answer = 7220
16 Correct 1 ms 296 KB Correct answer: answer = 7550
17 Correct 0 ms 204 KB Correct answer: answer = 10000
18 Correct 1 ms 204 KB Correct answer: answer = 10000
19 Correct 1 ms 204 KB Correct answer: answer = 624
20 Correct 0 ms 204 KB Correct answer: answer = 10000
21 Correct 0 ms 204 KB Correct answer: answer = 1
22 Correct 0 ms 204 KB Correct answer: answer = 4
23 Correct 1 ms 276 KB Correct answer: answer = 1
24 Correct 1 ms 204 KB Correct answer: answer = 5
25 Correct 0 ms 204 KB Correct answer: answer = 41
26 Correct 1 ms 204 KB Correct answer: answer = 71923
27 Correct 1 ms 204 KB Correct answer: answer = 77137
28 Correct 1 ms 332 KB Correct answer: answer = 764
29 Correct 1 ms 332 KB Correct answer: answer = 250000
30 Correct 1 ms 332 KB Correct answer: answer = 500
31 Correct 0 ms 292 KB Correct answer: answer = 32
32 Correct 1 ms 304 KB Correct answer: answer = 130050
33 Correct 1 ms 332 KB Correct answer: answer = 5110
34 Correct 1 ms 204 KB Correct answer: answer = 2626
35 Correct 1 ms 300 KB Correct answer: answer = 796
36 Correct 1 ms 336 KB Correct answer: answer = 7580
37 Correct 1 ms 332 KB Correct answer: answer = 1904
38 Correct 1 ms 204 KB Correct answer: answer = 996004
39 Correct 1 ms 204 KB Correct answer: answer = 38817
40 Correct 1 ms 292 KB Correct answer: answer = 4096
41 Correct 1 ms 204 KB Correct answer: answer = 1
42 Correct 0 ms 204 KB Correct answer: answer = 1
43 Correct 1 ms 332 KB Correct answer: answer = 2040
44 Correct 1 ms 204 KB Correct answer: answer = 2
45 Correct 0 ms 204 KB Correct answer: answer = 4
46 Correct 0 ms 204 KB Correct answer: answer = 9
47 Correct 0 ms 296 KB Correct answer: answer = 9
48 Correct 1 ms 204 KB Correct answer: answer = 21
49 Correct 1 ms 204 KB Correct answer: answer = 71
50 Correct 1 ms 204 KB Correct answer: answer = 77
51 Correct 1 ms 204 KB Correct answer: answer = 400
52 Correct 1 ms 300 KB Correct answer: answer = 996004
53 Correct 1 ms 204 KB Correct answer: answer = 997310
54 Correct 1 ms 204 KB Correct answer: answer = 990781
55 Correct 1 ms 304 KB Correct answer: answer = 996545
56 Correct 1 ms 204 KB Correct answer: answer = 484
57 Correct 1 ms 204 KB Correct answer: answer = 484
58 Correct 1 ms 304 KB Correct answer: answer = 63501
59 Correct 1 ms 332 KB Correct answer: answer = 323501
60 Correct 1 ms 296 KB Correct answer: answer = 752500
61 Correct 1 ms 204 KB Correct answer: answer = 761480
62 Correct 1 ms 204 KB Correct answer: answer = 758932
63 Correct 1 ms 296 KB Correct answer: answer = 1000000
64 Correct 2 ms 332 KB Correct answer: answer = 750500
65 Correct 1 ms 204 KB Correct answer: answer = 1000000
66 Correct 1 ms 204 KB Correct answer: answer = 250000
67 Correct 1 ms 204 KB Correct answer: answer = 250000
68 Correct 1 ms 296 KB Correct answer: answer = 1000000
69 Correct 1 ms 208 KB Correct answer: answer = 994009
70 Correct 1 ms 304 KB Correct answer: answer = 59315
71 Correct 1 ms 300 KB Correct answer: answer = 25454
72 Correct 1 ms 204 KB Correct answer: answer = 1504
73 Correct 1 ms 204 KB Correct answer: answer = 37486
74 Correct 1 ms 320 KB Correct answer: answer = 4284
75 Correct 1 ms 312 KB Correct answer: answer = 158008
76 Correct 1 ms 204 KB Correct answer: answer = 51860
77 Correct 1 ms 204 KB Correct answer: answer = 12985
78 Correct 2 ms 332 KB Correct answer: answer = 997864126212
79 Correct 1 ms 440 KB Correct answer: answer = 998608411647
80 Correct 2 ms 452 KB Correct answer: answer = 995265560477
81 Correct 6 ms 660 KB Correct answer: answer = 10125000
82 Correct 6 ms 680 KB Correct answer: answer = 2291668
83 Correct 2 ms 460 KB Correct answer: answer = 42388
84 Correct 3 ms 460 KB Correct answer: answer = 10318
85 Correct 3 ms 460 KB Correct answer: answer = 3416
86 Correct 14 ms 632 KB Correct answer: answer = 331708193881
87 Correct 8 ms 692 KB Correct answer: answer = 2861193756
88 Correct 7 ms 684 KB Correct answer: answer = 114646930
89 Correct 5 ms 728 KB Correct answer: answer = 9280921
90 Correct 5 ms 728 KB Correct answer: answer = 999984053400
91 Correct 6 ms 588 KB Correct answer: answer = 750935949134
92 Correct 1 ms 436 KB Correct answer: answer = 1000000000000
93 Correct 2 ms 332 KB Correct answer: answer = 998762383161
94 Correct 10 ms 620 KB Correct answer: answer = 23017412908
95 Correct 2 ms 332 KB Correct answer: answer = 728143410622
96 Correct 2 ms 332 KB Correct answer: answer = 2
97 Correct 9 ms 700 KB Correct answer: answer = 1824916
98 Correct 6 ms 564 KB Correct answer: answer = 10680029
99 Correct 8 ms 704 KB Correct answer: answer = 18351700
100 Correct 6 ms 676 KB Correct answer: answer = 16040026
101 Correct 2 ms 436 KB Correct answer: answer = 253968628325
102 Correct 4 ms 460 KB Correct answer: answer = 10267
103 Correct 6 ms 728 KB Correct answer: answer = 2582408
104 Correct 2 ms 332 KB Correct answer: answer = 78024964781
105 Correct 2 ms 332 KB Correct answer: answer = 9866346457
106 Correct 2 ms 460 KB Correct answer: answer = 3327720949
107 Correct 2 ms 440 KB Correct answer: answer = 86064128360
108 Correct 2 ms 460 KB Correct answer: answer = 12698259150
109 Correct 5 ms 704 KB Correct answer: answer = 1185259288
110 Correct 15 ms 2124 KB Correct answer: answer = 999889968863
111 Correct 14 ms 2124 KB Correct answer: answer = 999861384931
112 Correct 18 ms 2072 KB Correct answer: answer = 999811809929
113 Correct 14 ms 2092 KB Correct answer: answer = 999869756441
114 Correct 111 ms 5948 KB Correct answer: answer = 1700000000
115 Correct 115 ms 5896 KB Correct answer: answer = 131666670
116 Correct 35 ms 1936 KB Correct answer: answer = 89478486
117 Correct 24 ms 1984 KB Correct answer: answer = 4971040
118 Correct 21 ms 1992 KB Correct answer: answer = 2711494
119 Correct 97 ms 6048 KB Correct answer: answer = 25252530
120 Correct 129 ms 6000 KB Correct answer: answer = 62500000
121 Correct 160 ms 3108 KB Correct answer: answer = 333175097780
122 Correct 135 ms 3116 KB Correct answer: answer = 33121180179
123 Correct 113 ms 3056 KB Correct answer: answer = 9802314015
124 Correct 102 ms 6064 KB Correct answer: answer = 32567551
125 Correct 93 ms 6152 KB Correct answer: answer = 997525000000
126 Correct 96 ms 2892 KB Correct answer: answer = 752723538884
127 Correct 10 ms 2092 KB Correct answer: answer = 1000000000000
128 Correct 13 ms 2088 KB Correct answer: answer = 999978000121
129 Correct 18 ms 2092 KB Correct answer: answer = 745986144735
130 Correct 10 ms 1668 KB Correct answer: answer = 2
131 Correct 149 ms 5948 KB Correct answer: answer = 277966670
132 Correct 106 ms 5960 KB Correct answer: answer = 2500900082
133 Correct 26 ms 2208 KB Correct answer: answer = 301248349636
134 Correct 43 ms 2228 KB Correct answer: answer = 14118891
135 Correct 18 ms 2068 KB Correct answer: answer = 14384977265
136 Correct 18 ms 2116 KB Correct answer: answer = 3681368330
137 Correct 16 ms 2072 KB Correct answer: answer = 2720316816

Subtask #6
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Correct answer: answer = 4
2 Correct 0 ms 204 KB Correct answer: answer = 4
3 Correct 0 ms 204 KB Correct answer: answer = 4
4 Correct 1 ms 204 KB Correct answer: answer = 12
5 Correct 0 ms 204 KB Correct answer: answer = 52
6 Correct 0 ms 204 KB Correct answer: answer = 210
7 Correct 0 ms 204 KB Correct answer: answer = 88
8 Correct 1 ms 332 KB Correct answer: answer = 7696
9 Correct 0 ms 204 KB Correct answer: answer = 1
10 Correct 0 ms 204 KB Correct answer: answer = 2374
11 Correct 1 ms 204 KB Correct answer: answer = 9502
12 Correct 0 ms 204 KB Correct answer: answer = 49
13 Correct 1 ms 304 KB Correct answer: answer = 151
14 Correct 0 ms 204 KB Correct answer: answer = 7550
15 Correct 1 ms 204 KB Correct answer: answer = 7220
16 Correct 1 ms 296 KB Correct answer: answer = 7550
17 Correct 0 ms 204 KB Correct answer: answer = 10000
18 Correct 1 ms 204 KB Correct answer: answer = 10000
19 Correct 1 ms 204 KB Correct answer: answer = 624
20 Correct 0 ms 204 KB Correct answer: answer = 10000
21 Correct 0 ms 204 KB Correct answer: answer = 1
22 Correct 0 ms 204 KB Correct answer: answer = 4
23 Correct 1 ms 276 KB Correct answer: answer = 1
24 Correct 1 ms 204 KB Correct answer: answer = 5
25 Correct 0 ms 204 KB Correct answer: answer = 41
26 Correct 1 ms 204 KB Correct answer: answer = 71923
27 Correct 1 ms 204 KB Correct answer: answer = 77137
28 Correct 1 ms 332 KB Correct answer: answer = 764
29 Correct 1 ms 332 KB Correct answer: answer = 250000
30 Correct 1 ms 332 KB Correct answer: answer = 500
31 Correct 0 ms 292 KB Correct answer: answer = 32
32 Correct 1 ms 304 KB Correct answer: answer = 130050
33 Correct 1 ms 332 KB Correct answer: answer = 5110
34 Correct 1 ms 204 KB Correct answer: answer = 2626
35 Correct 1 ms 300 KB Correct answer: answer = 796
36 Correct 1 ms 336 KB Correct answer: answer = 7580
37 Correct 1 ms 332 KB Correct answer: answer = 1904
38 Correct 1 ms 204 KB Correct answer: answer = 996004
39 Correct 1 ms 204 KB Correct answer: answer = 38817
40 Correct 1 ms 292 KB Correct answer: answer = 4096
41 Correct 1 ms 204 KB Correct answer: answer = 1
42 Correct 0 ms 204 KB Correct answer: answer = 1
43 Correct 1 ms 332 KB Correct answer: answer = 2040
44 Correct 1 ms 204 KB Correct answer: answer = 2
45 Correct 0 ms 204 KB Correct answer: answer = 4
46 Correct 0 ms 204 KB Correct answer: answer = 9
47 Correct 0 ms 296 KB Correct answer: answer = 9
48 Correct 1 ms 204 KB Correct answer: answer = 21
49 Correct 1 ms 204 KB Correct answer: answer = 71
50 Correct 1 ms 204 KB Correct answer: answer = 77
51 Correct 1 ms 204 KB Correct answer: answer = 400
52 Correct 1 ms 300 KB Correct answer: answer = 996004
53 Correct 1 ms 204 KB Correct answer: answer = 997310
54 Correct 1 ms 204 KB Correct answer: answer = 990781
55 Correct 1 ms 304 KB Correct answer: answer = 996545
56 Correct 1 ms 204 KB Correct answer: answer = 484
57 Correct 1 ms 204 KB Correct answer: answer = 484
58 Correct 1 ms 304 KB Correct answer: answer = 63501
59 Correct 1 ms 332 KB Correct answer: answer = 323501
60 Correct 1 ms 296 KB Correct answer: answer = 752500
61 Correct 1 ms 204 KB Correct answer: answer = 761480
62 Correct 1 ms 204 KB Correct answer: answer = 758932
63 Correct 1 ms 296 KB Correct answer: answer = 1000000
64 Correct 2 ms 332 KB Correct answer: answer = 750500
65 Correct 1 ms 204 KB Correct answer: answer = 1000000
66 Correct 1 ms 204 KB Correct answer: answer = 250000
67 Correct 1 ms 204 KB Correct answer: answer = 250000
68 Correct 1 ms 296 KB Correct answer: answer = 1000000
69 Correct 1 ms 208 KB Correct answer: answer = 994009
70 Correct 1 ms 304 KB Correct answer: answer = 59315
71 Correct 1 ms 300 KB Correct answer: answer = 25454
72 Correct 1 ms 204 KB Correct answer: answer = 1504
73 Correct 1 ms 204 KB Correct answer: answer = 37486
74 Correct 1 ms 320 KB Correct answer: answer = 4284
75 Correct 1 ms 312 KB Correct answer: answer = 158008
76 Correct 1 ms 204 KB Correct answer: answer = 51860
77 Correct 1 ms 204 KB Correct answer: answer = 12985
78 Correct 2 ms 332 KB Correct answer: answer = 997864126212
79 Correct 1 ms 440 KB Correct answer: answer = 998608411647
80 Correct 2 ms 452 KB Correct answer: answer = 995265560477
81 Correct 6 ms 660 KB Correct answer: answer = 10125000
82 Correct 6 ms 680 KB Correct answer: answer = 2291668
83 Correct 2 ms 460 KB Correct answer: answer = 42388
84 Correct 3 ms 460 KB Correct answer: answer = 10318
85 Correct 3 ms 460 KB Correct answer: answer = 3416
86 Correct 14 ms 632 KB Correct answer: answer = 331708193881
87 Correct 8 ms 692 KB Correct answer: answer = 2861193756
88 Correct 7 ms 684 KB Correct answer: answer = 114646930
89 Correct 5 ms 728 KB Correct answer: answer = 9280921
90 Correct 5 ms 728 KB Correct answer: answer = 999984053400
91 Correct 6 ms 588 KB Correct answer: answer = 750935949134
92 Correct 1 ms 436 KB Correct answer: answer = 1000000000000
93 Correct 2 ms 332 KB Correct answer: answer = 998762383161
94 Correct 10 ms 620 KB Correct answer: answer = 23017412908
95 Correct 2 ms 332 KB Correct answer: answer = 728143410622
96 Correct 2 ms 332 KB Correct answer: answer = 2
97 Correct 9 ms 700 KB Correct answer: answer = 1824916
98 Correct 6 ms 564 KB Correct answer: answer = 10680029
99 Correct 8 ms 704 KB Correct answer: answer = 18351700
100 Correct 6 ms 676 KB Correct answer: answer = 16040026
101 Correct 2 ms 436 KB Correct answer: answer = 253968628325
102 Correct 4 ms 460 KB Correct answer: answer = 10267
103 Correct 6 ms 728 KB Correct answer: answer = 2582408
104 Correct 2 ms 332 KB Correct answer: answer = 78024964781
105 Correct 2 ms 332 KB Correct answer: answer = 9866346457
106 Correct 2 ms 460 KB Correct answer: answer = 3327720949
107 Correct 2 ms 440 KB Correct answer: answer = 86064128360
108 Correct 2 ms 460 KB Correct answer: answer = 12698259150
109 Correct 5 ms 704 KB Correct answer: answer = 1185259288
110 Correct 15 ms 2124 KB Correct answer: answer = 999889968863
111 Correct 14 ms 2124 KB Correct answer: answer = 999861384931
112 Correct 18 ms 2072 KB Correct answer: answer = 999811809929
113 Correct 14 ms 2092 KB Correct answer: answer = 999869756441
114 Correct 111 ms 5948 KB Correct answer: answer = 1700000000
115 Correct 115 ms 5896 KB Correct answer: answer = 131666670
116 Correct 35 ms 1936 KB Correct answer: answer = 89478486
117 Correct 24 ms 1984 KB Correct answer: answer = 4971040
118 Correct 21 ms 1992 KB Correct answer: answer = 2711494
119 Correct 97 ms 6048 KB Correct answer: answer = 25252530
120 Correct 129 ms 6000 KB Correct answer: answer = 62500000
121 Correct 160 ms 3108 KB Correct answer: answer = 333175097780
122 Correct 135 ms 3116 KB Correct answer: answer = 33121180179
123 Correct 113 ms 3056 KB Correct answer: answer = 9802314015
124 Correct 102 ms 6064 KB Correct answer: answer = 32567551
125 Correct 93 ms 6152 KB Correct answer: answer = 997525000000
126 Correct 96 ms 2892 KB Correct answer: answer = 752723538884
127 Correct 10 ms 2092 KB Correct answer: answer = 1000000000000
128 Correct 13 ms 2088 KB Correct answer: answer = 999978000121
129 Correct 18 ms 2092 KB Correct answer: answer = 745986144735
130 Correct 10 ms 1668 KB Correct answer: answer = 2
131 Correct 149 ms 5948 KB Correct answer: answer = 277966670
132 Correct 106 ms 5960 KB Correct answer: answer = 2500900082
133 Correct 26 ms 2208 KB Correct answer: answer = 301248349636
134 Correct 43 ms 2228 KB Correct answer: answer = 14118891
135 Correct 18 ms 2068 KB Correct answer: answer = 14384977265
136 Correct 18 ms 2116 KB Correct answer: answer = 3681368330
137 Correct 16 ms 2072 KB Correct answer: answer = 2720316816
138 Correct 27 ms 3916 KB Correct answer: answer = 999976000144
139 Correct 32 ms 3996 KB Correct answer: answer = 999856102410
140 Correct 28 ms 3956 KB Correct answer: answer = 999958401531
141 Correct 38 ms 3988 KB Correct answer: answer = 999769649944
142 Correct 29 ms 3992 KB Correct answer: answer = 999874525918
143 Correct 226 ms 11716 KB Correct answer: answer = 6050000000
144 Correct 398 ms 11680 KB Correct answer: answer = 1112500000
145 Correct 160 ms 7120 KB Correct answer: answer = 4294967296
146 Correct 186 ms 7120 KB Correct answer: answer = 87652406
147 Correct 97 ms 7244 KB Correct answer: answer = 6297664
148 Correct 96 ms 7232 KB Correct answer: answer = 196612
149 Correct 182 ms 11864 KB Correct answer: answer = 15015100
150 Correct 165 ms 11912 KB Correct answer: answer = 25000000
151 Correct 303 ms 5528 KB Correct answer: answer = 333230209550
152 Correct 150 ms 5552 KB Correct answer: answer = 917123769
153 Correct 181 ms 11920 KB Correct answer: answer = 95162
154 Correct 254 ms 11820 KB Correct answer: answer = 382616191
155 Correct 182 ms 11964 KB Correct answer: answer = 990033333400
156 Correct 175 ms 11968 KB Correct answer: answer = 990000100000
157 Correct 132 ms 10836 KB Correct answer: answer = 749998188180
158 Correct 20 ms 3888 KB Correct answer: answer = 1000000000000
159 Correct 26 ms 3956 KB Correct answer: answer = 999988000036
160 Correct 26 ms 4020 KB Correct answer: answer = 744929274393
161 Correct 18 ms 3000 KB Correct answer: answer = 2
162 Correct 182 ms 11960 KB Correct answer: answer = 1300024
163 Correct 237 ms 11732 KB Correct answer: answer = 5000700010
164 Correct 57 ms 4016 KB Correct answer: answer = 354997100800
165 Correct 82 ms 5524 KB Correct answer: answer = 257000
166 Correct 86 ms 6196 KB Correct answer: answer = 3765323
167 Correct 99 ms 6096 KB Correct answer: answer = 1525903
168 Correct 29 ms 3892 KB Correct answer: answer = 67618137730
169 Correct 30 ms 4016 KB Correct answer: answer = 12656680171
170 Correct 33 ms 3968 KB Correct answer: answer = 579831736
171 Correct 63 ms 5196 KB Correct answer: answer = 23605611
172 Correct 39 ms 4276 KB Correct answer: answer = 7052481200
173 Correct 56 ms 5060 KB Correct answer: answer = 1314039500
174 Correct 56 ms 5888 KB Correct answer: answer = 302484000
175 Correct 91 ms 6152 KB Correct answer: answer = 52348480