oj.uz

Submission #610956

# Submission time Handle Problem Language Result Execution time Memory
610956 2022-07-28T19:54:12 Z skittles1412 Aliens (IOI16_aliens) C++17
100 / 100
 1885 ms 55640 KB 
#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__);
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

using ll = long long;

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

struct Line {
    long m, b;
    int cnt;

    pair<long, int> operator()(long x) const {
        return {m * x + b, cnt};
    }

    friend ostream& operator<<(ostream& out, const Line& l) {
        return out << "Line {" << l.m << ", " << l.b << ", " << l.cnt << "}";
    }
};

struct BDS {
    vector<Line> arr;

    void clear() {
        arr.clear();
    }

    void update(Line x) {
        dbg(x);
        arr.push_back(x);
    }

    pair<long, int> query(int ind) {
        dbg(ind);
        auto ans = arr[0](ind);
        for (auto& a : arr) {
            ans = min(ans, a(ind));
        }
        return ans;
    }
} bds;

struct DS {
    static const int maxn = 1 << 20;
    Line v[maxn << 1];

    void clear() {
        fill(begin(v), end(v), Line {0, long(4e18), 0});
    }

    void update(int o, int l, int r, Line x) {
        int mid = (l + r) / 2, lc = o * 2, rc = lc + 1;
        if (x(mid) < v[o](mid)) {
            swap(v[o], x);
        }
        if (l == r) {
            return;
        }
        if (x(l) < v[o](l)) {
            update(lc, l, mid, x);
        } else {
            update(rc, mid + 1, r, x);
        }
    }

    void update(Line x) {
        update(1, 0, maxn - 1, x);
    }

    pair<long, int> query(int o, int l, int r, int ind) {
        int mid = (l + r) / 2, lc = o * 2, rc = lc + 1;
        auto ans = v[o](ind);
        if (l == r) {
            return ans;
        }
        if (ind <= mid) {
            ans = min(ans, query(lc, l, mid, ind));
        } else {
            ans = min(ans, query(rc, mid + 1, r, ind));
        }
        return ans;
    }

    pair<long, int> query(int ind) {
        dbg(ind);
        return query(1, 0, maxn - 1, ind);
    }
} ds;

int n;
vector<pair<int, int>> arr;

long sq(long x) {
    return x * x;
}

pair<long, int> solve(long x) {
    ds.clear();
    pair<long, int> dp[n + 1];
    auto upd = [&](int i) -> void {
        int r = arr[i - 1].second;
        ds.update({-2 * (r + 1), dp[i].first + sq(r + 1), dp[i].second});
    };
    dp[n] = {0, 0};
    upd(n);
    for (int i = n - 1; i >= 0; i--) {
        auto [cans, cnt] = ds.query(arr[i].first);
        dp[i] = {cans + x + sq(arr[i].first), cnt + 1};
        if (i && arr[i].first <= arr[i - 1].second) {
            dp[i].first -= sq(arr[i - 1].second - arr[i].first + 1);
        }
        if (i) {
            upd(i);
        }
        dbg(dp[i].first, dp[i].second);
    }
    return dp[0];
}

ll take_photos(int _n, int, int k, vector<int> a1, vector<int> a2) {
    n = _n;
    for (int i = 0; i < n; i++) {
        arr.emplace_back(min(a1[i], a2[i]), max(a1[i], a2[i]));
    }
    sort(begin(arr), end(arr), [&](pair<int, int> a, pair<int, int> b) -> bool {
        if (a.first == b.first) {
            return a.second > b.second;
        }
        return a.first < b.first;
    });
    vector<pair<int, int>> narr;
    int mx = -1;
    for (auto& [l, r] : arr) {
        if (r > mx) {
            mx = r;
            narr.emplace_back(l, r);
        }
    }
    swap(arr, narr);
    n = sz(arr);
    for (int i = 0; i < n - 1; i++) {
        assert(arr[i].first < arr[i + 1].first &&
               arr[i].second < arr[i + 1].second);
    }
    long l = 0, r = 1e18;
    while (l < r) {
        long mid = (l + r) / 2;
        if (solve(mid).second <= k) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    auto [x, cnt] = solve(l);
    dbg(l, x, cnt);
    return x - k * l;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 49524 KB Correct answer: answer = 4
2 Correct 387 ms 49536 KB Correct answer: answer = 4
3 Correct 391 ms 49520 KB Correct answer: answer = 4
4 Correct 373 ms 49532 KB Correct answer: answer = 12
5 Correct 403 ms 49492 KB Correct answer: answer = 52
6 Correct 376 ms 49532 KB Correct answer: answer = 210
7 Correct 397 ms 49528 KB Correct answer: answer = 88
8 Correct 383 ms 49612 KB Correct answer: answer = 7696
9 Correct 397 ms 49520 KB Correct answer: answer = 1
10 Correct 375 ms 49520 KB Correct answer: answer = 2374
11 Correct 378 ms 49524 KB Correct answer: answer = 9502
12 Correct 386 ms 49528 KB Correct answer: answer = 49
13 Correct 382 ms 49524 KB Correct answer: answer = 151
14 Correct 385 ms 49612 KB Correct answer: answer = 7550
15 Correct 383 ms 49524 KB Correct answer: answer = 7220
16 Correct 399 ms 49524 KB Correct answer: answer = 7550
17 Correct 382 ms 49524 KB Correct answer: answer = 10000
18 Correct 412 ms 49524 KB Correct answer: answer = 10000
19 Correct 390 ms 49536 KB Correct answer: answer = 624
20 Correct 374 ms 49520 KB Correct answer: answer = 10000

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 49612 KB Correct answer: answer = 1
2 Correct 402 ms 49520 KB Correct answer: answer = 4
3 Correct 387 ms 49520 KB Correct answer: answer = 1
4 Correct 416 ms 49520 KB Correct answer: answer = 5
5 Correct 421 ms 49524 KB Correct answer: answer = 41
6 Correct 394 ms 49520 KB Correct answer: answer = 71923
7 Correct 391 ms 49532 KB Correct answer: answer = 77137
8 Correct 403 ms 49548 KB Correct answer: answer = 764
9 Correct 397 ms 49544 KB Correct answer: answer = 250000
10 Correct 388 ms 49548 KB Correct answer: answer = 500
11 Correct 391 ms 49524 KB Correct answer: answer = 32
12 Correct 391 ms 49552 KB Correct answer: answer = 130050
13 Correct 395 ms 49548 KB Correct answer: answer = 5110
14 Correct 382 ms 49540 KB Correct answer: answer = 2626
15 Correct 388 ms 49532 KB Correct answer: answer = 796
16 Correct 391 ms 49548 KB Correct answer: answer = 7580
17 Correct 390 ms 49560 KB Correct answer: answer = 1904
18 Correct 386 ms 49540 KB Correct answer: answer = 996004
19 Correct 403 ms 49552 KB Correct answer: answer = 38817
20 Correct 395 ms 49544 KB Correct answer: answer = 4096
21 Correct 381 ms 49612 KB Correct answer: answer = 1
22 Correct 386 ms 49544 KB Correct answer: answer = 1
23 Correct 377 ms 49548 KB Correct answer: answer = 2040
24 Correct 383 ms 49544 KB Correct answer: answer = 2

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 49524 KB Correct answer: answer = 4
2 Correct 387 ms 49536 KB Correct answer: answer = 4
3 Correct 391 ms 49520 KB Correct answer: answer = 4
4 Correct 373 ms 49532 KB Correct answer: answer = 12
5 Correct 403 ms 49492 KB Correct answer: answer = 52
6 Correct 376 ms 49532 KB Correct answer: answer = 210
7 Correct 397 ms 49528 KB Correct answer: answer = 88
8 Correct 383 ms 49612 KB Correct answer: answer = 7696
9 Correct 397 ms 49520 KB Correct answer: answer = 1
10 Correct 375 ms 49520 KB Correct answer: answer = 2374
11 Correct 378 ms 49524 KB Correct answer: answer = 9502
12 Correct 386 ms 49528 KB Correct answer: answer = 49
13 Correct 382 ms 49524 KB Correct answer: answer = 151
14 Correct 385 ms 49612 KB Correct answer: answer = 7550
15 Correct 383 ms 49524 KB Correct answer: answer = 7220
16 Correct 399 ms 49524 KB Correct answer: answer = 7550
17 Correct 382 ms 49524 KB Correct answer: answer = 10000
18 Correct 412 ms 49524 KB Correct answer: answer = 10000
19 Correct 390 ms 49536 KB Correct answer: answer = 624
20 Correct 374 ms 49520 KB Correct answer: answer = 10000
21 Correct 382 ms 49612 KB Correct answer: answer = 1
22 Correct 402 ms 49520 KB Correct answer: answer = 4
23 Correct 387 ms 49520 KB Correct answer: answer = 1
24 Correct 416 ms 49520 KB Correct answer: answer = 5
25 Correct 421 ms 49524 KB Correct answer: answer = 41
26 Correct 394 ms 49520 KB Correct answer: answer = 71923
27 Correct 391 ms 49532 KB Correct answer: answer = 77137
28 Correct 403 ms 49548 KB Correct answer: answer = 764
29 Correct 397 ms 49544 KB Correct answer: answer = 250000
30 Correct 388 ms 49548 KB Correct answer: answer = 500
31 Correct 391 ms 49524 KB Correct answer: answer = 32
32 Correct 391 ms 49552 KB Correct answer: answer = 130050
33 Correct 395 ms 49548 KB Correct answer: answer = 5110
34 Correct 382 ms 49540 KB Correct answer: answer = 2626
35 Correct 388 ms 49532 KB Correct answer: answer = 796
36 Correct 391 ms 49548 KB Correct answer: answer = 7580
37 Correct 390 ms 49560 KB Correct answer: answer = 1904
38 Correct 386 ms 49540 KB Correct answer: answer = 996004
39 Correct 403 ms 49552 KB Correct answer: answer = 38817
40 Correct 395 ms 49544 KB Correct answer: answer = 4096
41 Correct 381 ms 49612 KB Correct answer: answer = 1
42 Correct 386 ms 49544 KB Correct answer: answer = 1
43 Correct 377 ms 49548 KB Correct answer: answer = 2040
44 Correct 383 ms 49544 KB Correct answer: answer = 2
45 Correct 375 ms 49524 KB Correct answer: answer = 4
46 Correct 413 ms 49520 KB Correct answer: answer = 9
47 Correct 378 ms 49524 KB Correct answer: answer = 9
48 Correct 385 ms 49520 KB Correct answer: answer = 21
49 Correct 405 ms 49524 KB Correct answer: answer = 71
50 Correct 395 ms 49520 KB Correct answer: answer = 77
51 Correct 433 ms 49524 KB Correct answer: answer = 400
52 Correct 498 ms 49536 KB Correct answer: answer = 996004
53 Correct 474 ms 49536 KB Correct answer: answer = 997310
54 Correct 523 ms 49492 KB Correct answer: answer = 990781
55 Correct 450 ms 49544 KB Correct answer: answer = 996545
56 Correct 383 ms 49540 KB Correct answer: answer = 484
57 Correct 385 ms 49540 KB Correct answer: answer = 484
58 Correct 382 ms 49548 KB Correct answer: answer = 63501
59 Correct 387 ms 49548 KB Correct answer: answer = 323501
60 Correct 384 ms 49548 KB Correct answer: answer = 752500
61 Correct 384 ms 49540 KB Correct answer: answer = 761480
62 Correct 384 ms 49536 KB Correct answer: answer = 758932
63 Correct 386 ms 49612 KB Correct answer: answer = 1000000
64 Correct 388 ms 49548 KB Correct answer: answer = 750500
65 Correct 384 ms 49536 KB Correct answer: answer = 1000000
66 Correct 380 ms 49540 KB Correct answer: answer = 250000
67 Correct 398 ms 49536 KB Correct answer: answer = 250000
68 Correct 382 ms 49540 KB Correct answer: answer = 1000000
69 Correct 400 ms 49500 KB Correct answer: answer = 994009
70 Correct 388 ms 49556 KB Correct answer: answer = 59315
71 Correct 374 ms 49540 KB Correct answer: answer = 25454
72 Correct 381 ms 49540 KB Correct answer: answer = 1504
73 Correct 384 ms 49528 KB Correct answer: answer = 37486
74 Correct 400 ms 49532 KB Correct answer: answer = 4284
75 Correct 391 ms 49536 KB Correct answer: answer = 158008
76 Correct 392 ms 49540 KB Correct answer: answer = 51860
77 Correct 387 ms 49544 KB Correct answer: answer = 12985

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 49524 KB Correct answer: answer = 4
2 Correct 387 ms 49536 KB Correct answer: answer = 4
3 Correct 391 ms 49520 KB Correct answer: answer = 4
4 Correct 373 ms 49532 KB Correct answer: answer = 12
5 Correct 403 ms 49492 KB Correct answer: answer = 52
6 Correct 376 ms 49532 KB Correct answer: answer = 210
7 Correct 397 ms 49528 KB Correct answer: answer = 88
8 Correct 383 ms 49612 KB Correct answer: answer = 7696
9 Correct 397 ms 49520 KB Correct answer: answer = 1
10 Correct 375 ms 49520 KB Correct answer: answer = 2374
11 Correct 378 ms 49524 KB Correct answer: answer = 9502
12 Correct 386 ms 49528 KB Correct answer: answer = 49
13 Correct 382 ms 49524 KB Correct answer: answer = 151
14 Correct 385 ms 49612 KB Correct answer: answer = 7550
15 Correct 383 ms 49524 KB Correct answer: answer = 7220
16 Correct 399 ms 49524 KB Correct answer: answer = 7550
17 Correct 382 ms 49524 KB Correct answer: answer = 10000
18 Correct 412 ms 49524 KB Correct answer: answer = 10000
19 Correct 390 ms 49536 KB Correct answer: answer = 624
20 Correct 374 ms 49520 KB Correct answer: answer = 10000
21 Correct 382 ms 49612 KB Correct answer: answer = 1
22 Correct 402 ms 49520 KB Correct answer: answer = 4
23 Correct 387 ms 49520 KB Correct answer: answer = 1
24 Correct 416 ms 49520 KB Correct answer: answer = 5
25 Correct 421 ms 49524 KB Correct answer: answer = 41
26 Correct 394 ms 49520 KB Correct answer: answer = 71923
27 Correct 391 ms 49532 KB Correct answer: answer = 77137
28 Correct 403 ms 49548 KB Correct answer: answer = 764
29 Correct 397 ms 49544 KB Correct answer: answer = 250000
30 Correct 388 ms 49548 KB Correct answer: answer = 500
31 Correct 391 ms 49524 KB Correct answer: answer = 32
32 Correct 391 ms 49552 KB Correct answer: answer = 130050
33 Correct 395 ms 49548 KB Correct answer: answer = 5110
34 Correct 382 ms 49540 KB Correct answer: answer = 2626
35 Correct 388 ms 49532 KB Correct answer: answer = 796
36 Correct 391 ms 49548 KB Correct answer: answer = 7580
37 Correct 390 ms 49560 KB Correct answer: answer = 1904
38 Correct 386 ms 49540 KB Correct answer: answer = 996004
39 Correct 403 ms 49552 KB Correct answer: answer = 38817
40 Correct 395 ms 49544 KB Correct answer: answer = 4096
41 Correct 381 ms 49612 KB Correct answer: answer = 1
42 Correct 386 ms 49544 KB Correct answer: answer = 1
43 Correct 377 ms 49548 KB Correct answer: answer = 2040
44 Correct 383 ms 49544 KB Correct answer: answer = 2
45 Correct 375 ms 49524 KB Correct answer: answer = 4
46 Correct 413 ms 49520 KB Correct answer: answer = 9
47 Correct 378 ms 49524 KB Correct answer: answer = 9
48 Correct 385 ms 49520 KB Correct answer: answer = 21
49 Correct 405 ms 49524 KB Correct answer: answer = 71
50 Correct 395 ms 49520 KB Correct answer: answer = 77
51 Correct 433 ms 49524 KB Correct answer: answer = 400
52 Correct 498 ms 49536 KB Correct answer: answer = 996004
53 Correct 474 ms 49536 KB Correct answer: answer = 997310
54 Correct 523 ms 49492 KB Correct answer: answer = 990781
55 Correct 450 ms 49544 KB Correct answer: answer = 996545
56 Correct 383 ms 49540 KB Correct answer: answer = 484
57 Correct 385 ms 49540 KB Correct answer: answer = 484
58 Correct 382 ms 49548 KB Correct answer: answer = 63501
59 Correct 387 ms 49548 KB Correct answer: answer = 323501
60 Correct 384 ms 49548 KB Correct answer: answer = 752500
61 Correct 384 ms 49540 KB Correct answer: answer = 761480
62 Correct 384 ms 49536 KB Correct answer: answer = 758932
63 Correct 386 ms 49612 KB Correct answer: answer = 1000000
64 Correct 388 ms 49548 KB Correct answer: answer = 750500
65 Correct 384 ms 49536 KB Correct answer: answer = 1000000
66 Correct 380 ms 49540 KB Correct answer: answer = 250000
67 Correct 398 ms 49536 KB Correct answer: answer = 250000
68 Correct 382 ms 49540 KB Correct answer: answer = 1000000
69 Correct 400 ms 49500 KB Correct answer: answer = 994009
70 Correct 388 ms 49556 KB Correct answer: answer = 59315
71 Correct 374 ms 49540 KB Correct answer: answer = 25454
72 Correct 381 ms 49540 KB Correct answer: answer = 1504
73 Correct 384 ms 49528 KB Correct answer: answer = 37486
74 Correct 400 ms 49532 KB Correct answer: answer = 4284
75 Correct 391 ms 49536 KB Correct answer: answer = 158008
76 Correct 392 ms 49540 KB Correct answer: answer = 51860
77 Correct 387 ms 49544 KB Correct answer: answer = 12985
78 Correct 381 ms 49652 KB Correct answer: answer = 997864126212
79 Correct 390 ms 49652 KB Correct answer: answer = 998608411647
80 Correct 396 ms 49648 KB Correct answer: answer = 995265560477
81 Correct 414 ms 49744 KB Correct answer: answer = 10125000
82 Correct 430 ms 49748 KB Correct answer: answer = 2291668
83 Correct 403 ms 49636 KB Correct answer: answer = 42388
84 Correct 398 ms 49648 KB Correct answer: answer = 10318
85 Correct 400 ms 49636 KB Correct answer: answer = 3416
86 Correct 462 ms 49740 KB Correct answer: answer = 331708193881
87 Correct 495 ms 49744 KB Correct answer: answer = 2861193756
88 Correct 492 ms 49748 KB Correct answer: answer = 114646930
89 Correct 431 ms 49748 KB Correct answer: answer = 9280921
90 Correct 427 ms 49748 KB Correct answer: answer = 999984053400
91 Correct 476 ms 49748 KB Correct answer: answer = 750935949134
92 Correct 392 ms 49656 KB Correct answer: answer = 1000000000000
93 Correct 386 ms 49740 KB Correct answer: answer = 998762383161
94 Correct 468 ms 49764 KB Correct answer: answer = 23017412908
95 Correct 386 ms 49652 KB Correct answer: answer = 728143410622
96 Correct 388 ms 49656 KB Correct answer: answer = 2
97 Correct 424 ms 49792 KB Correct answer: answer = 1824916
98 Correct 437 ms 49736 KB Correct answer: answer = 10680029
99 Correct 452 ms 49748 KB Correct answer: answer = 18351700
100 Correct 429 ms 49740 KB Correct answer: answer = 16040026
101 Correct 387 ms 49620 KB Correct answer: answer = 253968628325
102 Correct 410 ms 49632 KB Correct answer: answer = 10267
103 Correct 445 ms 49744 KB Correct answer: answer = 2582408
104 Correct 390 ms 49652 KB Correct answer: answer = 78024964781
105 Correct 381 ms 49648 KB Correct answer: answer = 9866346457
106 Correct 392 ms 49688 KB Correct answer: answer = 3327720949
107 Correct 388 ms 49612 KB Correct answer: answer = 86064128360
108 Correct 406 ms 49656 KB Correct answer: answer = 12698259150
109 Correct 462 ms 49728 KB Correct answer: answer = 1185259288

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 49524 KB Correct answer: answer = 4
2 Correct 387 ms 49536 KB Correct answer: answer = 4
3 Correct 391 ms 49520 KB Correct answer: answer = 4
4 Correct 373 ms 49532 KB Correct answer: answer = 12
5 Correct 403 ms 49492 KB Correct answer: answer = 52
6 Correct 376 ms 49532 KB Correct answer: answer = 210
7 Correct 397 ms 49528 KB Correct answer: answer = 88
8 Correct 383 ms 49612 KB Correct answer: answer = 7696
9 Correct 397 ms 49520 KB Correct answer: answer = 1
10 Correct 375 ms 49520 KB Correct answer: answer = 2374
11 Correct 378 ms 49524 KB Correct answer: answer = 9502
12 Correct 386 ms 49528 KB Correct answer: answer = 49
13 Correct 382 ms 49524 KB Correct answer: answer = 151
14 Correct 385 ms 49612 KB Correct answer: answer = 7550
15 Correct 383 ms 49524 KB Correct answer: answer = 7220
16 Correct 399 ms 49524 KB Correct answer: answer = 7550
17 Correct 382 ms 49524 KB Correct answer: answer = 10000
18 Correct 412 ms 49524 KB Correct answer: answer = 10000
19 Correct 390 ms 49536 KB Correct answer: answer = 624
20 Correct 374 ms 49520 KB Correct answer: answer = 10000
21 Correct 382 ms 49612 KB Correct answer: answer = 1
22 Correct 402 ms 49520 KB Correct answer: answer = 4
23 Correct 387 ms 49520 KB Correct answer: answer = 1
24 Correct 416 ms 49520 KB Correct answer: answer = 5
25 Correct 421 ms 49524 KB Correct answer: answer = 41
26 Correct 394 ms 49520 KB Correct answer: answer = 71923
27 Correct 391 ms 49532 KB Correct answer: answer = 77137
28 Correct 403 ms 49548 KB Correct answer: answer = 764
29 Correct 397 ms 49544 KB Correct answer: answer = 250000
30 Correct 388 ms 49548 KB Correct answer: answer = 500
31 Correct 391 ms 49524 KB Correct answer: answer = 32
32 Correct 391 ms 49552 KB Correct answer: answer = 130050
33 Correct 395 ms 49548 KB Correct answer: answer = 5110
34 Correct 382 ms 49540 KB Correct answer: answer = 2626
35 Correct 388 ms 49532 KB Correct answer: answer = 796
36 Correct 391 ms 49548 KB Correct answer: answer = 7580
37 Correct 390 ms 49560 KB Correct answer: answer = 1904
38 Correct 386 ms 49540 KB Correct answer: answer = 996004
39 Correct 403 ms 49552 KB Correct answer: answer = 38817
40 Correct 395 ms 49544 KB Correct answer: answer = 4096
41 Correct 381 ms 49612 KB Correct answer: answer = 1
42 Correct 386 ms 49544 KB Correct answer: answer = 1
43 Correct 377 ms 49548 KB Correct answer: answer = 2040
44 Correct 383 ms 49544 KB Correct answer: answer = 2
45 Correct 375 ms 49524 KB Correct answer: answer = 4
46 Correct 413 ms 49520 KB Correct answer: answer = 9
47 Correct 378 ms 49524 KB Correct answer: answer = 9
48 Correct 385 ms 49520 KB Correct answer: answer = 21
49 Correct 405 ms 49524 KB Correct answer: answer = 71
50 Correct 395 ms 49520 KB Correct answer: answer = 77
51 Correct 433 ms 49524 KB Correct answer: answer = 400
52 Correct 498 ms 49536 KB Correct answer: answer = 996004
53 Correct 474 ms 49536 KB Correct answer: answer = 997310
54 Correct 523 ms 49492 KB Correct answer: answer = 990781
55 Correct 450 ms 49544 KB Correct answer: answer = 996545
56 Correct 383 ms 49540 KB Correct answer: answer = 484
57 Correct 385 ms 49540 KB Correct answer: answer = 484
58 Correct 382 ms 49548 KB Correct answer: answer = 63501
59 Correct 387 ms 49548 KB Correct answer: answer = 323501
60 Correct 384 ms 49548 KB Correct answer: answer = 752500
61 Correct 384 ms 49540 KB Correct answer: answer = 761480
62 Correct 384 ms 49536 KB Correct answer: answer = 758932
63 Correct 386 ms 49612 KB Correct answer: answer = 1000000
64 Correct 388 ms 49548 KB Correct answer: answer = 750500
65 Correct 384 ms 49536 KB Correct answer: answer = 1000000
66 Correct 380 ms 49540 KB Correct answer: answer = 250000
67 Correct 398 ms 49536 KB Correct answer: answer = 250000
68 Correct 382 ms 49540 KB Correct answer: answer = 1000000
69 Correct 400 ms 49500 KB Correct answer: answer = 994009
70 Correct 388 ms 49556 KB Correct answer: answer = 59315
71 Correct 374 ms 49540 KB Correct answer: answer = 25454
72 Correct 381 ms 49540 KB Correct answer: answer = 1504
73 Correct 384 ms 49528 KB Correct answer: answer = 37486
74 Correct 400 ms 49532 KB Correct answer: answer = 4284
75 Correct 391 ms 49536 KB Correct answer: answer = 158008
76 Correct 392 ms 49540 KB Correct answer: answer = 51860
77 Correct 387 ms 49544 KB Correct answer: answer = 12985
78 Correct 381 ms 49652 KB Correct answer: answer = 997864126212
79 Correct 390 ms 49652 KB Correct answer: answer = 998608411647
80 Correct 396 ms 49648 KB Correct answer: answer = 995265560477
81 Correct 414 ms 49744 KB Correct answer: answer = 10125000
82 Correct 430 ms 49748 KB Correct answer: answer = 2291668
83 Correct 403 ms 49636 KB Correct answer: answer = 42388
84 Correct 398 ms 49648 KB Correct answer: answer = 10318
85 Correct 400 ms 49636 KB Correct answer: answer = 3416
86 Correct 462 ms 49740 KB Correct answer: answer = 331708193881
87 Correct 495 ms 49744 KB Correct answer: answer = 2861193756
88 Correct 492 ms 49748 KB Correct answer: answer = 114646930
89 Correct 431 ms 49748 KB Correct answer: answer = 9280921
90 Correct 427 ms 49748 KB Correct answer: answer = 999984053400
91 Correct 476 ms 49748 KB Correct answer: answer = 750935949134
92 Correct 392 ms 49656 KB Correct answer: answer = 1000000000000
93 Correct 386 ms 49740 KB Correct answer: answer = 998762383161
94 Correct 468 ms 49764 KB Correct answer: answer = 23017412908
95 Correct 386 ms 49652 KB Correct answer: answer = 728143410622
96 Correct 388 ms 49656 KB Correct answer: answer = 2
97 Correct 424 ms 49792 KB Correct answer: answer = 1824916
98 Correct 437 ms 49736 KB Correct answer: answer = 10680029
99 Correct 452 ms 49748 KB Correct answer: answer = 18351700
100 Correct 429 ms 49740 KB Correct answer: answer = 16040026
101 Correct 387 ms 49620 KB Correct answer: answer = 253968628325
102 Correct 410 ms 49632 KB Correct answer: answer = 10267
103 Correct 445 ms 49744 KB Correct answer: answer = 2582408
104 Correct 390 ms 49652 KB Correct answer: answer = 78024964781
105 Correct 381 ms 49648 KB Correct answer: answer = 9866346457
106 Correct 392 ms 49688 KB Correct answer: answer = 3327720949
107 Correct 388 ms 49612 KB Correct answer: answer = 86064128360
108 Correct 406 ms 49656 KB Correct answer: answer = 12698259150
109 Correct 462 ms 49728 KB Correct answer: answer = 1185259288
110 Correct 418 ms 50760 KB Correct answer: answer = 999889968863
111 Correct 416 ms 50812 KB Correct answer: answer = 999861384931
112 Correct 403 ms 50764 KB Correct answer: answer = 999811809929
113 Correct 400 ms 50756 KB Correct answer: answer = 999869756441
114 Correct 865 ms 51940 KB Correct answer: answer = 1700000000
115 Correct 902 ms 52580 KB Correct answer: answer = 131666670
116 Correct 553 ms 50612 KB Correct answer: answer = 89478486
117 Correct 567 ms 50612 KB Correct answer: answer = 4971040
118 Correct 548 ms 50616 KB Correct answer: answer = 2711494
119 Correct 921 ms 52588 KB Correct answer: answer = 25252530
120 Correct 901 ms 52584 KB Correct answer: answer = 62500000
121 Correct 1135 ms 52676 KB Correct answer: answer = 333175097780
122 Correct 1193 ms 52672 KB Correct answer: answer = 33121180179
123 Correct 1201 ms 52668 KB Correct answer: answer = 9802314015
124 Correct 883 ms 52588 KB Correct answer: answer = 32567551
125 Correct 938 ms 52644 KB Correct answer: answer = 997525000000
126 Correct 1058 ms 52608 KB Correct answer: answer = 752723538884
127 Correct 385 ms 51404 KB Correct answer: answer = 1000000000000
128 Correct 402 ms 51612 KB Correct answer: answer = 999978000121
129 Correct 393 ms 51468 KB Correct answer: answer = 745986144735
130 Correct 385 ms 50940 KB Correct answer: answer = 2
131 Correct 913 ms 52552 KB Correct answer: answer = 277966670
132 Correct 852 ms 52584 KB Correct answer: answer = 2500900082
133 Correct 476 ms 51524 KB Correct answer: answer = 301248349636
134 Correct 661 ms 51124 KB Correct answer: answer = 14118891
135 Correct 394 ms 51368 KB Correct answer: answer = 14384977265
136 Correct 427 ms 51488 KB Correct answer: answer = 3681368330
137 Correct 419 ms 51396 KB Correct answer: answer = 2720316816

Subtask #6
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 49524 KB Correct answer: answer = 4
2 Correct 387 ms 49536 KB Correct answer: answer = 4
3 Correct 391 ms 49520 KB Correct answer: answer = 4
4 Correct 373 ms 49532 KB Correct answer: answer = 12
5 Correct 403 ms 49492 KB Correct answer: answer = 52
6 Correct 376 ms 49532 KB Correct answer: answer = 210
7 Correct 397 ms 49528 KB Correct answer: answer = 88
8 Correct 383 ms 49612 KB Correct answer: answer = 7696
9 Correct 397 ms 49520 KB Correct answer: answer = 1
10 Correct 375 ms 49520 KB Correct answer: answer = 2374
11 Correct 378 ms 49524 KB Correct answer: answer = 9502
12 Correct 386 ms 49528 KB Correct answer: answer = 49
13 Correct 382 ms 49524 KB Correct answer: answer = 151
14 Correct 385 ms 49612 KB Correct answer: answer = 7550
15 Correct 383 ms 49524 KB Correct answer: answer = 7220
16 Correct 399 ms 49524 KB Correct answer: answer = 7550
17 Correct 382 ms 49524 KB Correct answer: answer = 10000
18 Correct 412 ms 49524 KB Correct answer: answer = 10000
19 Correct 390 ms 49536 KB Correct answer: answer = 624
20 Correct 374 ms 49520 KB Correct answer: answer = 10000
21 Correct 382 ms 49612 KB Correct answer: answer = 1
22 Correct 402 ms 49520 KB Correct answer: answer = 4
23 Correct 387 ms 49520 KB Correct answer: answer = 1
24 Correct 416 ms 49520 KB Correct answer: answer = 5
25 Correct 421 ms 49524 KB Correct answer: answer = 41
26 Correct 394 ms 49520 KB Correct answer: answer = 71923
27 Correct 391 ms 49532 KB Correct answer: answer = 77137
28 Correct 403 ms 49548 KB Correct answer: answer = 764
29 Correct 397 ms 49544 KB Correct answer: answer = 250000
30 Correct 388 ms 49548 KB Correct answer: answer = 500
31 Correct 391 ms 49524 KB Correct answer: answer = 32
32 Correct 391 ms 49552 KB Correct answer: answer = 130050
33 Correct 395 ms 49548 KB Correct answer: answer = 5110
34 Correct 382 ms 49540 KB Correct answer: answer = 2626
35 Correct 388 ms 49532 KB Correct answer: answer = 796
36 Correct 391 ms 49548 KB Correct answer: answer = 7580
37 Correct 390 ms 49560 KB Correct answer: answer = 1904
38 Correct 386 ms 49540 KB Correct answer: answer = 996004
39 Correct 403 ms 49552 KB Correct answer: answer = 38817
40 Correct 395 ms 49544 KB Correct answer: answer = 4096
41 Correct 381 ms 49612 KB Correct answer: answer = 1
42 Correct 386 ms 49544 KB Correct answer: answer = 1
43 Correct 377 ms 49548 KB Correct answer: answer = 2040
44 Correct 383 ms 49544 KB Correct answer: answer = 2
45 Correct 375 ms 49524 KB Correct answer: answer = 4
46 Correct 413 ms 49520 KB Correct answer: answer = 9
47 Correct 378 ms 49524 KB Correct answer: answer = 9
48 Correct 385 ms 49520 KB Correct answer: answer = 21
49 Correct 405 ms 49524 KB Correct answer: answer = 71
50 Correct 395 ms 49520 KB Correct answer: answer = 77
51 Correct 433 ms 49524 KB Correct answer: answer = 400
52 Correct 498 ms 49536 KB Correct answer: answer = 996004
53 Correct 474 ms 49536 KB Correct answer: answer = 997310
54 Correct 523 ms 49492 KB Correct answer: answer = 990781
55 Correct 450 ms 49544 KB Correct answer: answer = 996545
56 Correct 383 ms 49540 KB Correct answer: answer = 484
57 Correct 385 ms 49540 KB Correct answer: answer = 484
58 Correct 382 ms 49548 KB Correct answer: answer = 63501
59 Correct 387 ms 49548 KB Correct answer: answer = 323501
60 Correct 384 ms 49548 KB Correct answer: answer = 752500
61 Correct 384 ms 49540 KB Correct answer: answer = 761480
62 Correct 384 ms 49536 KB Correct answer: answer = 758932
63 Correct 386 ms 49612 KB Correct answer: answer = 1000000
64 Correct 388 ms 49548 KB Correct answer: answer = 750500
65 Correct 384 ms 49536 KB Correct answer: answer = 1000000
66 Correct 380 ms 49540 KB Correct answer: answer = 250000
67 Correct 398 ms 49536 KB Correct answer: answer = 250000
68 Correct 382 ms 49540 KB Correct answer: answer = 1000000
69 Correct 400 ms 49500 KB Correct answer: answer = 994009
70 Correct 388 ms 49556 KB Correct answer: answer = 59315
71 Correct 374 ms 49540 KB Correct answer: answer = 25454
72 Correct 381 ms 49540 KB Correct answer: answer = 1504
73 Correct 384 ms 49528 KB Correct answer: answer = 37486
74 Correct 400 ms 49532 KB Correct answer: answer = 4284
75 Correct 391 ms 49536 KB Correct answer: answer = 158008
76 Correct 392 ms 49540 KB Correct answer: answer = 51860
77 Correct 387 ms 49544 KB Correct answer: answer = 12985
78 Correct 381 ms 49652 KB Correct answer: answer = 997864126212
79 Correct 390 ms 49652 KB Correct answer: answer = 998608411647
80 Correct 396 ms 49648 KB Correct answer: answer = 995265560477
81 Correct 414 ms 49744 KB Correct answer: answer = 10125000
82 Correct 430 ms 49748 KB Correct answer: answer = 2291668
83 Correct 403 ms 49636 KB Correct answer: answer = 42388
84 Correct 398 ms 49648 KB Correct answer: answer = 10318
85 Correct 400 ms 49636 KB Correct answer: answer = 3416
86 Correct 462 ms 49740 KB Correct answer: answer = 331708193881
87 Correct 495 ms 49744 KB Correct answer: answer = 2861193756
88 Correct 492 ms 49748 KB Correct answer: answer = 114646930
89 Correct 431 ms 49748 KB Correct answer: answer = 9280921
90 Correct 427 ms 49748 KB Correct answer: answer = 999984053400
91 Correct 476 ms 49748 KB Correct answer: answer = 750935949134
92 Correct 392 ms 49656 KB Correct answer: answer = 1000000000000
93 Correct 386 ms 49740 KB Correct answer: answer = 998762383161
94 Correct 468 ms 49764 KB Correct answer: answer = 23017412908
95 Correct 386 ms 49652 KB Correct answer: answer = 728143410622
96 Correct 388 ms 49656 KB Correct answer: answer = 2
97 Correct 424 ms 49792 KB Correct answer: answer = 1824916
98 Correct 437 ms 49736 KB Correct answer: answer = 10680029
99 Correct 452 ms 49748 KB Correct answer: answer = 18351700
100 Correct 429 ms 49740 KB Correct answer: answer = 16040026
101 Correct 387 ms 49620 KB Correct answer: answer = 253968628325
102 Correct 410 ms 49632 KB Correct answer: answer = 10267
103 Correct 445 ms 49744 KB Correct answer: answer = 2582408
104 Correct 390 ms 49652 KB Correct answer: answer = 78024964781
105 Correct 381 ms 49648 KB Correct answer: answer = 9866346457
106 Correct 392 ms 49688 KB Correct answer: answer = 3327720949
107 Correct 388 ms 49612 KB Correct answer: answer = 86064128360
108 Correct 406 ms 49656 KB Correct answer: answer = 12698259150
109 Correct 462 ms 49728 KB Correct answer: answer = 1185259288
110 Correct 418 ms 50760 KB Correct answer: answer = 999889968863
111 Correct 416 ms 50812 KB Correct answer: answer = 999861384931
112 Correct 403 ms 50764 KB Correct answer: answer = 999811809929
113 Correct 400 ms 50756 KB Correct answer: answer = 999869756441
114 Correct 865 ms 51940 KB Correct answer: answer = 1700000000
115 Correct 902 ms 52580 KB Correct answer: answer = 131666670
116 Correct 553 ms 50612 KB Correct answer: answer = 89478486
117 Correct 567 ms 50612 KB Correct answer: answer = 4971040
118 Correct 548 ms 50616 KB Correct answer: answer = 2711494
119 Correct 921 ms 52588 KB Correct answer: answer = 25252530
120 Correct 901 ms 52584 KB Correct answer: answer = 62500000
121 Correct 1135 ms 52676 KB Correct answer: answer = 333175097780
122 Correct 1193 ms 52672 KB Correct answer: answer = 33121180179
123 Correct 1201 ms 52668 KB Correct answer: answer = 9802314015
124 Correct 883 ms 52588 KB Correct answer: answer = 32567551
125 Correct 938 ms 52644 KB Correct answer: answer = 997525000000
126 Correct 1058 ms 52608 KB Correct answer: answer = 752723538884
127 Correct 385 ms 51404 KB Correct answer: answer = 1000000000000
128 Correct 402 ms 51612 KB Correct answer: answer = 999978000121
129 Correct 393 ms 51468 KB Correct answer: answer = 745986144735
130 Correct 385 ms 50940 KB Correct answer: answer = 2
131 Correct 913 ms 52552 KB Correct answer: answer = 277966670
132 Correct 852 ms 52584 KB Correct answer: answer = 2500900082
133 Correct 476 ms 51524 KB Correct answer: answer = 301248349636
134 Correct 661 ms 51124 KB Correct answer: answer = 14118891
135 Correct 394 ms 51368 KB Correct answer: answer = 14384977265
136 Correct 427 ms 51488 KB Correct answer: answer = 3681368330
137 Correct 419 ms 51396 KB Correct answer: answer = 2720316816
138 Correct 410 ms 53304 KB Correct answer: answer = 999976000144
139 Correct 418 ms 53292 KB Correct answer: answer = 999856102410
140 Correct 419 ms 53288 KB Correct answer: answer = 999958401531
141 Correct 415 ms 53312 KB Correct answer: answer = 999769649944
142 Correct 425 ms 53272 KB Correct answer: answer = 999874525918
143 Correct 1432 ms 55636 KB Correct answer: answer = 6050000000
144 Correct 1519 ms 55548 KB Correct answer: answer = 1112500000
145 Correct 1068 ms 53516 KB Correct answer: answer = 4294967296
146 Correct 1171 ms 53444 KB Correct answer: answer = 87652406
147 Correct 1137 ms 53540 KB Correct answer: answer = 6297664
148 Correct 1114 ms 53516 KB Correct answer: answer = 196612
149 Correct 1420 ms 55528 KB Correct answer: answer = 15015100
150 Correct 1431 ms 55524 KB Correct answer: answer = 25000000
151 Correct 1761 ms 55608 KB Correct answer: answer = 333230209550
152 Correct 1885 ms 55608 KB Correct answer: answer = 917123769
153 Correct 1834 ms 55608 KB Correct answer: answer = 95162
154 Correct 1497 ms 55536 KB Correct answer: answer = 382616191
155 Correct 1455 ms 55632 KB Correct answer: answer = 990033333400
156 Correct 1455 ms 55640 KB Correct answer: answer = 990000100000
157 Correct 1502 ms 55376 KB Correct answer: answer = 749998188180
158 Correct 406 ms 53240 KB Correct answer: answer = 1000000000000
159 Correct 405 ms 53280 KB Correct answer: answer = 999988000036
160 Correct 415 ms 53296 KB Correct answer: answer = 744929274393
161 Correct 407 ms 52320 KB Correct answer: answer = 2
162 Correct 1464 ms 55524 KB Correct answer: answer = 1300024
163 Correct 1432 ms 55528 KB Correct answer: answer = 5000700010
164 Correct 555 ms 53440 KB Correct answer: answer = 354997100800
165 Correct 947 ms 52592 KB Correct answer: answer = 257000
166 Correct 1137 ms 52704 KB Correct answer: answer = 3765323
167 Correct 998 ms 52640 KB Correct answer: answer = 1525903
168 Correct 433 ms 53312 KB Correct answer: answer = 67618137730
169 Correct 405 ms 53248 KB Correct answer: answer = 12656680171
170 Correct 472 ms 53288 KB Correct answer: answer = 579831736
171 Correct 869 ms 54052 KB Correct answer: answer = 23605611
172 Correct 482 ms 53376 KB Correct answer: answer = 7052481200
173 Correct 610 ms 53568 KB Correct answer: answer = 1314039500
174 Correct 761 ms 53932 KB Correct answer: answer = 302484000
175 Correct 1342 ms 55040 KB Correct answer: answer = 52348480