oj.uz

Submission #568262

# Submission time Handle Problem Language Result Execution time Memory
568262 2022-05-25T04:03:05 Z ngpin04 Aliens (IOI16_aliens) C++17
100 / 100
 183 ms 9424 KB 
#include "aliens.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
    if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
    if (a < b) {a = b; return true;} return false;
}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) {
    return l + rd() % (r - l + 1);
}
const int N = 2e5 + 5; 
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);

vector <pair <int, long long>> seg;
vector <long double> inter;
vector <int> ind;

pair <int, int> a[N];

long long dp[N];

int ptr[N];
int cnt[N];
int n,m,k,sz,cur;

typedef long long ll;

long double intersect(pair <int, ll> a, pair <int, ll> b) {
    return (long double) (b.se - a.se) / (a.fi - b.fi);
}

bool good(pair <int, ll> a, pair <int, ll> b, pair <int, ll> c) {
    long double xM = intersect(a, c);
    long double xN = intersect(b, c);
    return xM < xN;
}

void addLine(pair <int, ll> s, int i) {
    while (sz > 1 && !good(seg[sz - 2], seg[sz - 1], s)) {
        seg.pop_back();
        inter.pop_back();
        ind.pop_back();
        sz--;
    }

    if (sz > 0)
        inter.push_back(intersect(s, seg.back()));
    seg.push_back(s);
    ind.push_back(i);
    sz++;
    mini(cur, sz - 2);
}

int getopt(int x) {
    while (cur + 1 < (int) inter.size() && x > inter[cur + 1])
        cur++;
    // cerr << x << " " << cur << "\n";
    return cur;
}

int solve(long long cost) {
    sz = 0;
    inter.clear();
    seg.clear();
    ind.clear();
    inter.push_back(-ooo);
    
    a[n + 1] = mp(oo, oo);
    for (int i = 1; i <= n; i++) {
        long long add = 1LL * (a[i].se + 1) * (a[i].se + 1);
        long long sub = 0;
        if (a[i].se >= a[i + 1].fi) {
            int d = a[i].se - a[i + 1].fi + 1;
            sub = 1LL * d * d;
        }

        long long y = (dp[i - 1] + 1LL * a[i].fi * a[i].fi) + cost;
        int x = -2 * a[i].fi;
        addLine(mp(x, y), i - 1);

        int it = -1;
        // long long res = ooo;
        // for (int j = 0; j < sz; j++) 
        //     if (mini(res, 1LL * seg[j].fi * (a[i].se + 1) 
        //     + seg[j].se - sub + add))
        //         it = j;

        it = getopt(a[i].se + 1);
        dp[i] = 1LL * seg[it].fi * (a[i].se + 1) + seg[it].se - sub + add;
        cnt[i] = cnt[ind[it]] + 1;
        ptr[i] = ind[it];
    }
    return cnt[n];
}

long long solve() {

    long long lo = -1;
    long long hi = 1e12 + 123;
    while (hi - lo > 1) {
        long long mid = (lo + hi) >> 1;
        if (solve(mid) > k)
            lo = mid;
        else
            hi = mid;
    }

    solve(hi);
    return dp[n] - k * hi;
}

void build() {
    for (int i = 1; i <= n; i++)
        if (a[i].fi > a[i].se)
            swap(a[i].fi, a[i].se);
    
    sort(a + 1, a + n + 1, [](pair <int, int> a, pair <int, int> b) {
        return (a.fi < b.fi) || (a.fi == b.fi && a.se > b.se);
    });

    int cur = -oo;
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i].se > cur) {
            cur = a[i].se;
            a[++cnt] = a[i];
        }
    }
    n = cnt;
}

long long take_photos(int _n, int _m, int _k, vector<int> r, vector<int> c) {
    n = _n;
    m = _m;
    k = _k;
    for (int i = 1; i <= n; i++)
        a[i] = mp(r[i - 1], c[i - 1]);
    build();
    return solve();
}

//#include "grader.cpp"

Subtask #1
4.0 / 4.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
16.0 / 16.0

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

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Correct answer: answer = 4
2 Correct 1 ms 212 KB Correct answer: answer = 4
3 Correct 0 ms 212 KB Correct answer: answer = 4
4 Correct 1 ms 340 KB Correct answer: answer = 12
5 Correct 1 ms 212 KB Correct answer: answer = 52
6 Correct 1 ms 212 KB Correct answer: answer = 210
7 Correct 1 ms 212 KB Correct answer: answer = 88
8 Correct 1 ms 212 KB Correct answer: answer = 7696
9 Correct 1 ms 212 KB Correct answer: answer = 1
10 Correct 1 ms 212 KB Correct answer: answer = 2374
11 Correct 1 ms 212 KB Correct answer: answer = 9502
12 Correct 1 ms 212 KB Correct answer: answer = 49
13 Correct 1 ms 312 KB Correct answer: answer = 151
14 Correct 1 ms 308 KB Correct answer: answer = 7550
15 Correct 1 ms 312 KB Correct answer: answer = 7220
16 Correct 1 ms 340 KB Correct answer: answer = 7550
17 Correct 1 ms 212 KB Correct answer: answer = 10000
18 Correct 1 ms 212 KB Correct answer: answer = 10000
19 Correct 1 ms 212 KB Correct answer: answer = 624
20 Correct 1 ms 212 KB Correct answer: answer = 10000
21 Correct 1 ms 212 KB Correct answer: answer = 1
22 Correct 1 ms 340 KB Correct answer: answer = 4
23 Correct 1 ms 212 KB Correct answer: answer = 1
24 Correct 1 ms 212 KB Correct answer: answer = 5
25 Correct 1 ms 340 KB Correct answer: answer = 41
26 Correct 1 ms 212 KB Correct answer: answer = 71923
27 Correct 1 ms 340 KB Correct answer: answer = 77137
28 Correct 1 ms 340 KB Correct answer: answer = 764
29 Correct 1 ms 304 KB Correct answer: answer = 250000
30 Correct 1 ms 340 KB Correct answer: answer = 500
31 Correct 0 ms 212 KB Correct answer: answer = 32
32 Correct 1 ms 340 KB Correct answer: answer = 130050
33 Correct 1 ms 340 KB Correct answer: answer = 5110
34 Correct 1 ms 312 KB Correct answer: answer = 2626
35 Correct 1 ms 308 KB Correct answer: answer = 796
36 Correct 1 ms 340 KB Correct answer: answer = 7580
37 Correct 1 ms 340 KB Correct answer: answer = 1904
38 Correct 1 ms 340 KB Correct answer: answer = 996004
39 Correct 1 ms 340 KB Correct answer: answer = 38817
40 Correct 1 ms 312 KB Correct answer: answer = 4096
41 Correct 1 ms 340 KB Correct answer: answer = 1
42 Correct 1 ms 340 KB Correct answer: answer = 1
43 Correct 1 ms 340 KB Correct answer: answer = 2040
44 Correct 1 ms 340 KB Correct answer: answer = 2
45 Correct 1 ms 308 KB Correct answer: answer = 4
46 Correct 1 ms 212 KB Correct answer: answer = 9
47 Correct 0 ms 212 KB Correct answer: answer = 9
48 Correct 1 ms 264 KB Correct answer: answer = 21
49 Correct 0 ms 340 KB Correct answer: answer = 71
50 Correct 0 ms 212 KB Correct answer: answer = 77
51 Correct 1 ms 212 KB Correct answer: answer = 400
52 Correct 1 ms 340 KB Correct answer: answer = 996004
53 Correct 1 ms 340 KB Correct answer: answer = 997310
54 Correct 1 ms 340 KB Correct answer: answer = 990781
55 Correct 1 ms 340 KB Correct answer: answer = 996545
56 Correct 1 ms 340 KB Correct answer: answer = 484
57 Correct 1 ms 316 KB Correct answer: answer = 484
58 Correct 1 ms 312 KB Correct answer: answer = 63501
59 Correct 1 ms 340 KB Correct answer: answer = 323501
60 Correct 1 ms 340 KB Correct answer: answer = 752500
61 Correct 1 ms 312 KB Correct answer: answer = 761480
62 Correct 1 ms 340 KB Correct answer: answer = 758932
63 Correct 1 ms 340 KB Correct answer: answer = 1000000
64 Correct 1 ms 340 KB Correct answer: answer = 750500
65 Correct 1 ms 312 KB Correct answer: answer = 1000000
66 Correct 1 ms 340 KB Correct answer: answer = 250000
67 Correct 1 ms 340 KB Correct answer: answer = 250000
68 Correct 1 ms 308 KB Correct answer: answer = 1000000
69 Correct 1 ms 340 KB Correct answer: answer = 994009
70 Correct 1 ms 340 KB Correct answer: answer = 59315
71 Correct 1 ms 316 KB Correct answer: answer = 25454
72 Correct 1 ms 340 KB Correct answer: answer = 1504
73 Correct 1 ms 340 KB Correct answer: answer = 37486
74 Correct 1 ms 340 KB Correct answer: answer = 4284
75 Correct 1 ms 340 KB Correct answer: answer = 158008
76 Correct 1 ms 312 KB Correct answer: answer = 51860
77 Correct 1 ms 312 KB Correct answer: answer = 12985
78 Correct 2 ms 468 KB Correct answer: answer = 997864126212
79 Correct 2 ms 468 KB Correct answer: answer = 998608411647
80 Correct 2 ms 468 KB Correct answer: answer = 995265560477
81 Correct 5 ms 596 KB Correct answer: answer = 10125000
82 Correct 5 ms 596 KB Correct answer: answer = 2291668
83 Correct 4 ms 456 KB Correct answer: answer = 42388
84 Correct 4 ms 516 KB Correct answer: answer = 10318
85 Correct 5 ms 468 KB Correct answer: answer = 3416
86 Correct 8 ms 468 KB Correct answer: answer = 331708193881
87 Correct 8 ms 468 KB Correct answer: answer = 2861193756
88 Correct 9 ms 596 KB Correct answer: answer = 114646930
89 Correct 6 ms 640 KB Correct answer: answer = 9280921
90 Correct 5 ms 724 KB Correct answer: answer = 999984053400
91 Correct 8 ms 596 KB Correct answer: answer = 750935949134
92 Correct 1 ms 468 KB Correct answer: answer = 1000000000000
93 Correct 2 ms 396 KB Correct answer: answer = 998762383161
94 Correct 8 ms 552 KB Correct answer: answer = 23017412908
95 Correct 2 ms 448 KB Correct answer: answer = 728143410622
96 Correct 1 ms 340 KB Correct answer: answer = 2
97 Correct 6 ms 644 KB Correct answer: answer = 1824916
98 Correct 6 ms 580 KB Correct answer: answer = 10680029
99 Correct 6 ms 668 KB Correct answer: answer = 18351700
100 Correct 5 ms 596 KB Correct answer: answer = 16040026
101 Correct 2 ms 468 KB Correct answer: answer = 253968628325
102 Correct 3 ms 468 KB Correct answer: answer = 10267
103 Correct 6 ms 724 KB Correct answer: answer = 2582408
104 Correct 2 ms 468 KB Correct answer: answer = 78024964781
105 Correct 2 ms 400 KB Correct answer: answer = 9866346457
106 Correct 2 ms 396 KB Correct answer: answer = 3327720949
107 Correct 2 ms 468 KB Correct answer: answer = 86064128360
108 Correct 2 ms 448 KB Correct answer: answer = 12698259150
109 Correct 5 ms 596 KB Correct answer: answer = 1185259288
110 Correct 15 ms 2144 KB Correct answer: answer = 999889968863
111 Correct 15 ms 2180 KB Correct answer: answer = 999861384931
112 Correct 16 ms 2104 KB Correct answer: answer = 999811809929
113 Correct 17 ms 2112 KB Correct answer: answer = 999869756441
114 Correct 63 ms 3728 KB Correct answer: answer = 1700000000
115 Correct 63 ms 4512 KB Correct answer: answer = 131666670
116 Correct 20 ms 1620 KB Correct answer: answer = 89478486
117 Correct 20 ms 1828 KB Correct answer: answer = 4971040
118 Correct 19 ms 1828 KB Correct answer: answer = 2711494
119 Correct 61 ms 4644 KB Correct answer: answer = 25252530
120 Correct 58 ms 4664 KB Correct answer: answer = 62500000
121 Correct 89 ms 3020 KB Correct answer: answer = 333175097780
122 Correct 91 ms 2904 KB Correct answer: answer = 33121180179
123 Correct 93 ms 3120 KB Correct answer: answer = 9802314015
124 Correct 66 ms 4624 KB Correct answer: answer = 32567551
125 Correct 61 ms 4684 KB Correct answer: answer = 997525000000
126 Correct 92 ms 2892 KB Correct answer: answer = 752723538884
127 Correct 10 ms 2104 KB Correct answer: answer = 1000000000000
128 Correct 16 ms 2160 KB Correct answer: answer = 999978000121
129 Correct 16 ms 2116 KB Correct answer: answer = 745986144735
130 Correct 9 ms 1680 KB Correct answer: answer = 2
131 Correct 63 ms 4604 KB Correct answer: answer = 277966670
132 Correct 63 ms 3908 KB Correct answer: answer = 2500900082
133 Correct 23 ms 2104 KB Correct answer: answer = 301248349636
134 Correct 38 ms 2140 KB Correct answer: answer = 14118891
135 Correct 15 ms 2132 KB Correct answer: answer = 14384977265
136 Correct 16 ms 2148 KB Correct answer: answer = 3681368330
137 Correct 17 ms 2144 KB Correct answer: answer = 2720316816

Subtask #6
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Correct answer: answer = 4
2 Correct 1 ms 212 KB Correct answer: answer = 4
3 Correct 0 ms 212 KB Correct answer: answer = 4
4 Correct 1 ms 340 KB Correct answer: answer = 12
5 Correct 1 ms 212 KB Correct answer: answer = 52
6 Correct 1 ms 212 KB Correct answer: answer = 210
7 Correct 1 ms 212 KB Correct answer: answer = 88
8 Correct 1 ms 212 KB Correct answer: answer = 7696
9 Correct 1 ms 212 KB Correct answer: answer = 1
10 Correct 1 ms 212 KB Correct answer: answer = 2374
11 Correct 1 ms 212 KB Correct answer: answer = 9502
12 Correct 1 ms 212 KB Correct answer: answer = 49
13 Correct 1 ms 312 KB Correct answer: answer = 151
14 Correct 1 ms 308 KB Correct answer: answer = 7550
15 Correct 1 ms 312 KB Correct answer: answer = 7220
16 Correct 1 ms 340 KB Correct answer: answer = 7550
17 Correct 1 ms 212 KB Correct answer: answer = 10000
18 Correct 1 ms 212 KB Correct answer: answer = 10000
19 Correct 1 ms 212 KB Correct answer: answer = 624
20 Correct 1 ms 212 KB Correct answer: answer = 10000
21 Correct 1 ms 212 KB Correct answer: answer = 1
22 Correct 1 ms 340 KB Correct answer: answer = 4
23 Correct 1 ms 212 KB Correct answer: answer = 1
24 Correct 1 ms 212 KB Correct answer: answer = 5
25 Correct 1 ms 340 KB Correct answer: answer = 41
26 Correct 1 ms 212 KB Correct answer: answer = 71923
27 Correct 1 ms 340 KB Correct answer: answer = 77137
28 Correct 1 ms 340 KB Correct answer: answer = 764
29 Correct 1 ms 304 KB Correct answer: answer = 250000
30 Correct 1 ms 340 KB Correct answer: answer = 500
31 Correct 0 ms 212 KB Correct answer: answer = 32
32 Correct 1 ms 340 KB Correct answer: answer = 130050
33 Correct 1 ms 340 KB Correct answer: answer = 5110
34 Correct 1 ms 312 KB Correct answer: answer = 2626
35 Correct 1 ms 308 KB Correct answer: answer = 796
36 Correct 1 ms 340 KB Correct answer: answer = 7580
37 Correct 1 ms 340 KB Correct answer: answer = 1904
38 Correct 1 ms 340 KB Correct answer: answer = 996004
39 Correct 1 ms 340 KB Correct answer: answer = 38817
40 Correct 1 ms 312 KB Correct answer: answer = 4096
41 Correct 1 ms 340 KB Correct answer: answer = 1
42 Correct 1 ms 340 KB Correct answer: answer = 1
43 Correct 1 ms 340 KB Correct answer: answer = 2040
44 Correct 1 ms 340 KB Correct answer: answer = 2
45 Correct 1 ms 308 KB Correct answer: answer = 4
46 Correct 1 ms 212 KB Correct answer: answer = 9
47 Correct 0 ms 212 KB Correct answer: answer = 9
48 Correct 1 ms 264 KB Correct answer: answer = 21
49 Correct 0 ms 340 KB Correct answer: answer = 71
50 Correct 0 ms 212 KB Correct answer: answer = 77
51 Correct 1 ms 212 KB Correct answer: answer = 400
52 Correct 1 ms 340 KB Correct answer: answer = 996004
53 Correct 1 ms 340 KB Correct answer: answer = 997310
54 Correct 1 ms 340 KB Correct answer: answer = 990781
55 Correct 1 ms 340 KB Correct answer: answer = 996545
56 Correct 1 ms 340 KB Correct answer: answer = 484
57 Correct 1 ms 316 KB Correct answer: answer = 484
58 Correct 1 ms 312 KB Correct answer: answer = 63501
59 Correct 1 ms 340 KB Correct answer: answer = 323501
60 Correct 1 ms 340 KB Correct answer: answer = 752500
61 Correct 1 ms 312 KB Correct answer: answer = 761480
62 Correct 1 ms 340 KB Correct answer: answer = 758932
63 Correct 1 ms 340 KB Correct answer: answer = 1000000
64 Correct 1 ms 340 KB Correct answer: answer = 750500
65 Correct 1 ms 312 KB Correct answer: answer = 1000000
66 Correct 1 ms 340 KB Correct answer: answer = 250000
67 Correct 1 ms 340 KB Correct answer: answer = 250000
68 Correct 1 ms 308 KB Correct answer: answer = 1000000
69 Correct 1 ms 340 KB Correct answer: answer = 994009
70 Correct 1 ms 340 KB Correct answer: answer = 59315
71 Correct 1 ms 316 KB Correct answer: answer = 25454
72 Correct 1 ms 340 KB Correct answer: answer = 1504
73 Correct 1 ms 340 KB Correct answer: answer = 37486
74 Correct 1 ms 340 KB Correct answer: answer = 4284
75 Correct 1 ms 340 KB Correct answer: answer = 158008
76 Correct 1 ms 312 KB Correct answer: answer = 51860
77 Correct 1 ms 312 KB Correct answer: answer = 12985
78 Correct 2 ms 468 KB Correct answer: answer = 997864126212
79 Correct 2 ms 468 KB Correct answer: answer = 998608411647
80 Correct 2 ms 468 KB Correct answer: answer = 995265560477
81 Correct 5 ms 596 KB Correct answer: answer = 10125000
82 Correct 5 ms 596 KB Correct answer: answer = 2291668
83 Correct 4 ms 456 KB Correct answer: answer = 42388
84 Correct 4 ms 516 KB Correct answer: answer = 10318
85 Correct 5 ms 468 KB Correct answer: answer = 3416
86 Correct 8 ms 468 KB Correct answer: answer = 331708193881
87 Correct 8 ms 468 KB Correct answer: answer = 2861193756
88 Correct 9 ms 596 KB Correct answer: answer = 114646930
89 Correct 6 ms 640 KB Correct answer: answer = 9280921
90 Correct 5 ms 724 KB Correct answer: answer = 999984053400
91 Correct 8 ms 596 KB Correct answer: answer = 750935949134
92 Correct 1 ms 468 KB Correct answer: answer = 1000000000000
93 Correct 2 ms 396 KB Correct answer: answer = 998762383161
94 Correct 8 ms 552 KB Correct answer: answer = 23017412908
95 Correct 2 ms 448 KB Correct answer: answer = 728143410622
96 Correct 1 ms 340 KB Correct answer: answer = 2
97 Correct 6 ms 644 KB Correct answer: answer = 1824916
98 Correct 6 ms 580 KB Correct answer: answer = 10680029
99 Correct 6 ms 668 KB Correct answer: answer = 18351700
100 Correct 5 ms 596 KB Correct answer: answer = 16040026
101 Correct 2 ms 468 KB Correct answer: answer = 253968628325
102 Correct 3 ms 468 KB Correct answer: answer = 10267
103 Correct 6 ms 724 KB Correct answer: answer = 2582408
104 Correct 2 ms 468 KB Correct answer: answer = 78024964781
105 Correct 2 ms 400 KB Correct answer: answer = 9866346457
106 Correct 2 ms 396 KB Correct answer: answer = 3327720949
107 Correct 2 ms 468 KB Correct answer: answer = 86064128360
108 Correct 2 ms 448 KB Correct answer: answer = 12698259150
109 Correct 5 ms 596 KB Correct answer: answer = 1185259288
110 Correct 15 ms 2144 KB Correct answer: answer = 999889968863
111 Correct 15 ms 2180 KB Correct answer: answer = 999861384931
112 Correct 16 ms 2104 KB Correct answer: answer = 999811809929
113 Correct 17 ms 2112 KB Correct answer: answer = 999869756441
114 Correct 63 ms 3728 KB Correct answer: answer = 1700000000
115 Correct 63 ms 4512 KB Correct answer: answer = 131666670
116 Correct 20 ms 1620 KB Correct answer: answer = 89478486
117 Correct 20 ms 1828 KB Correct answer: answer = 4971040
118 Correct 19 ms 1828 KB Correct answer: answer = 2711494
119 Correct 61 ms 4644 KB Correct answer: answer = 25252530
120 Correct 58 ms 4664 KB Correct answer: answer = 62500000
121 Correct 89 ms 3020 KB Correct answer: answer = 333175097780
122 Correct 91 ms 2904 KB Correct answer: answer = 33121180179
123 Correct 93 ms 3120 KB Correct answer: answer = 9802314015
124 Correct 66 ms 4624 KB Correct answer: answer = 32567551
125 Correct 61 ms 4684 KB Correct answer: answer = 997525000000
126 Correct 92 ms 2892 KB Correct answer: answer = 752723538884
127 Correct 10 ms 2104 KB Correct answer: answer = 1000000000000
128 Correct 16 ms 2160 KB Correct answer: answer = 999978000121
129 Correct 16 ms 2116 KB Correct answer: answer = 745986144735
130 Correct 9 ms 1680 KB Correct answer: answer = 2
131 Correct 63 ms 4604 KB Correct answer: answer = 277966670
132 Correct 63 ms 3908 KB Correct answer: answer = 2500900082
133 Correct 23 ms 2104 KB Correct answer: answer = 301248349636
134 Correct 38 ms 2140 KB Correct answer: answer = 14118891
135 Correct 15 ms 2132 KB Correct answer: answer = 14384977265
136 Correct 16 ms 2148 KB Correct answer: answer = 3681368330
137 Correct 17 ms 2144 KB Correct answer: answer = 2720316816
138 Correct 31 ms 3916 KB Correct answer: answer = 999976000144
139 Correct 31 ms 3900 KB Correct answer: answer = 999856102410
140 Correct 30 ms 3900 KB Correct answer: answer = 999958401531
141 Correct 33 ms 3900 KB Correct answer: answer = 999769649944
142 Correct 30 ms 3920 KB Correct answer: answer = 999874525918
143 Correct 132 ms 7168 KB Correct answer: answer = 6050000000
144 Correct 124 ms 8864 KB Correct answer: answer = 1112500000
145 Correct 74 ms 5312 KB Correct answer: answer = 4294967296
146 Correct 80 ms 6036 KB Correct answer: answer = 87652406
147 Correct 78 ms 6036 KB Correct answer: answer = 6297664
148 Correct 81 ms 6100 KB Correct answer: answer = 196612
149 Correct 118 ms 9248 KB Correct answer: answer = 15015100
150 Correct 111 ms 9348 KB Correct answer: answer = 25000000
151 Correct 172 ms 5524 KB Correct answer: answer = 333230209550
152 Correct 183 ms 5784 KB Correct answer: answer = 917123769
153 Correct 176 ms 9364 KB Correct answer: answer = 95162
154 Correct 127 ms 9132 KB Correct answer: answer = 382616191
155 Correct 128 ms 9392 KB Correct answer: answer = 990033333400
156 Correct 122 ms 9424 KB Correct answer: answer = 990000100000
157 Correct 162 ms 7692 KB Correct answer: answer = 749998188180
158 Correct 20 ms 3916 KB Correct answer: answer = 1000000000000
159 Correct 29 ms 4012 KB Correct answer: answer = 999988000036
160 Correct 30 ms 4024 KB Correct answer: answer = 744929274393
161 Correct 17 ms 3028 KB Correct answer: answer = 2
162 Correct 135 ms 9292 KB Correct answer: answer = 1300024
163 Correct 122 ms 7480 KB Correct answer: answer = 5000700010
164 Correct 46 ms 4032 KB Correct answer: answer = 354997100800
165 Correct 77 ms 4572 KB Correct answer: answer = 257000
166 Correct 73 ms 4752 KB Correct answer: answer = 3765323
167 Correct 78 ms 4792 KB Correct answer: answer = 1525903
168 Correct 32 ms 4020 KB Correct answer: answer = 67618137730
169 Correct 32 ms 3916 KB Correct answer: answer = 12656680171
170 Correct 34 ms 4024 KB Correct answer: answer = 579831736
171 Correct 72 ms 5052 KB Correct answer: answer = 23605611
172 Correct 34 ms 4284 KB Correct answer: answer = 7052481200
173 Correct 43 ms 4680 KB Correct answer: answer = 1314039500
174 Correct 51 ms 5284 KB Correct answer: answer = 302484000
175 Correct 95 ms 5956 KB Correct answer: answer = 52348480