oj.uz

Submission #504198

# Submission time Handle Problem Language Result Execution time Memory
504198 2022-01-10T01:50:47 Z maximumSHOT Aliens (IOI16_aliens) C++17
100 / 100
 246 ms 9728 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ui = unsigned int;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<long long, long long>;

const int inf = 1e9;
const ll inf64 = 1e18;

struct output {
    ll res;

    void print() {
        cout << res << "\n";
    }

    bool operator == (const output& o) const {
        return res == o.res;
    }
};

struct input {
    int n, m, k;
    vector<pii> a;

    input() = default;

    void read() {
        cin >> n >> m >> k;
        a.resize(n);
        for (auto& [x, y] : a)
            cin >> x >> y;
    }

    void print() {
        cout << n << " " << m << " " << k << "\n";
        for (auto [x, y] : a)
            cout << x << " " << y << "\n";
    }

    void gen() {
        static mt19937 rnd(42);
        const int MAXN = 100;
        n = rnd() % MAXN + 1;
        m = rnd() % MAXN + 1;
        k = rnd() % n + 1;
        a.resize(n);
        for (auto& [x, y] : a) {
            x = rnd() % m;
            y = rnd() % m;
        }
    }

    void gen_max_test() {

    }

    void prepare() {
        for (auto& [x, y] : a) {
            if (y > x)
                swap(x, y);
        }
        vector<pii> st;
        sort(a.begin(), a.end());
        for (int i = 0; i < n; i++) {
            if (i > 0 && a[i].first == a[i - 1].first)
                continue;
            while (!st.empty() && st.back().second >= a[i].second)
                st.pop_back();
            st.push_back(a[i]);
        }
        a = st;
        n = (int) a.size();
    }

    ll f(int len) {
        return 1ll * len * len;
    }

    struct Line {
        ll k = 0;
        ll b = 0;
        int c = 0;

        ld intersect(const Line& o) const {
            return ld(o.b - b) / ld(k - o.k);
        }

        ll f(ll x) const {
            return k * x + b;
        }
    };

    output fast() {
        prepare();
        vector<ll> rem(n);
        for (int j = 0; j < n; j++)
            rem[j] = f(max(0, (j > 0 ? a[j - 1].first : -1) - a[j].second + 1));
        vector<pair<ll, int>> dp(n);

        vector<Line> lines(n);
        for (int j = 0; j < n; j++) {
            lines[j] = {
                -2ll * a[j].second,
                (j > 0 ? dp[j - 1].first : 0ll) + 1ll * a[j].second * a[j].second - rem[j]
            };
        }

        auto calc = [&](ll lambda) -> pair<ll, int> {
            deque<Line> st;
            for (int i = 0; i < n; i++) {
                dp[i] = {inf64, inf};
                ll CONST = lambda + 1ll * (a[i].first + 1) * (a[i].first + 1);
                ll x0 = a[i].first + 1;
                lines[i] = {
                    -2ll * a[i].second,
                    (i > 0 ? dp[i - 1].first : 0ll) + 1ll * a[i].second * a[i].second - rem[i],
                    (i > 0 ? dp[i - 1].second : 0)
                };
                while ((int) st.size() >= 2) {
                    Line L1 = st[(int) st.size() - 2];
                    Line L2 = st[(int) st.size() - 1];
                    if (L1.intersect(L2) < L2.intersect(lines[i]))
                        break;
                    st.pop_back();
                }
                st.push_back(lines[i]);
                while ((int) st.size() >= 2 && st[0].intersect(st[1]) < x0)
                    st.pop_front();
                dp[i] = {
                    CONST + st[0].f(x0),
                    st[0].c - 1
                };
                if ((int) st.size() > 1) {
                    dp[i] = min(dp[i], make_pair(CONST + st[1].f(x0), st[1].c - 1));
                }
//                for (Line line : st) {
//                    dp[i] = min(dp[i], make_pair(
//                            CONST + line.f(x0),
//                            line.c - 1
//                    ));
//                }
//                for (int j = i; j >= 0; j--) {
//                    dp[i] = min(dp[i], make_pair(
//                        CONST + lines[j].k * x0 + lines[j].b,
//                        lines[j].c - 1
//                    ));
//                }
            }
            return dp[n - 1];
        };
        ll bl = 0, br = 1ll * m * m + 10, bm;
        while (br - bl > 1) {
            bm = bl + (br - bl) / 2;
            auto tmp = calc(bm);
            if (-tmp.second >= k) bl = bm;
            else br = bm;
        }
        ll lambda = bl;
        auto tmp = calc(lambda);
        ll res = tmp.first - lambda * k;
        return output{res};
    }

    output slow() {
#ifndef DEBUG
        throw;
#endif
        prepare();
        vector<vector<ll>> dp(n, vector<ll>(k + 1, inf64));
        for (int i = 0; i < n; i++) {
            for (int j = i; j >= 0; j--) {
                ll cost =
                        f(a[i].first - a[j].second + 1) -
                        f(max(0, (j > 0 ? a[j - 1].first : -1) - a[j].second + 1));
                for (int c = 1; c <= k; c++)
                    dp[i][c] = min(dp[i][c], (j > 0 ? dp[j - 1][c - 1] : 0) + cost);
            }
        }
        ll res = inf64;
        for (int c = 1; c <= k; c++)
            res = min(res, dp[n - 1][c]);
        return output{res};
    }
};

void test_case() {
    input in;
    in.read();
    output res = in.fast();
    res.print();
}

void work() {
    int t = 1;
    while (t--)
        test_case();
}

void test() {
    for (int t = 1;;t++) {
        input in;
        in.gen();
        input in_fs = in;
        input in_sl = in;
        output fs = in_fs.fast();
        output sl = in_sl.slow();
        if (fs == sl) {
            cout << "OK" << endl;
            fs.print();
            cout << "\n=========" << endl;
        } else {
            cout << "WA " << t << "\n";
            cout << "exp\n";
            sl.print();
            cout << "\n=========\n";
            cout << "fnd\n";
            fs.print();
            cout << "\n=========\n";
            in.print();
            break;
        }
    }
}

void max_test() {
    input in;
    in.gen_max_test();
    input in_fs = in;
    output fs = in_fs.fast();
    fs.print();
}

#ifdef DEBUG

int main() {

#ifdef DEBUG
    freopen("input.txt", "r", stdin);
#endif

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    work();
//    test();
//    max_test();

    return 0;
}
#else

ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
    input in;
    in.n = n;
    in.m = m;
    in.k = k;
    in.a.resize(n);
    for (int i = 0; i < n; i++)
        in.a[i] = {r[i], c[i]};
    output fs = in.fast();
    return fs.res;
}

#endif

Compilation message

aliens.cpp: In function 'void max_test()':
aliens.cpp:27:8: warning: 'in.input::k' is used uninitialized in this function [-Wuninitialized]
   27 | struct input {
      |        ^~~~~
aliens.cpp:27:8: warning: 'in' is used uninitialized in this function [-Wuninitialized]

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Correct answer: answer = 4
2 Correct 1 ms 292 KB Correct answer: answer = 4
3 Correct 0 ms 204 KB Correct answer: answer = 4
4 Correct 0 ms 204 KB Correct answer: answer = 12
5 Correct 0 ms 204 KB Correct answer: answer = 52
6 Correct 0 ms 208 KB Correct answer: answer = 210
7 Correct 0 ms 204 KB Correct answer: answer = 88
8 Correct 0 ms 204 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 1 ms 204 KB Correct answer: answer = 49
13 Correct 1 ms 204 KB Correct answer: answer = 151
14 Correct 1 ms 204 KB Correct answer: answer = 7550
15 Correct 0 ms 204 KB Correct answer: answer = 7220
16 Correct 0 ms 204 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 0 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 296 KB Correct answer: answer = 4
3 Correct 0 ms 204 KB Correct answer: answer = 1
4 Correct 0 ms 204 KB Correct answer: answer = 5
5 Correct 0 ms 204 KB Correct answer: answer = 41
6 Correct 0 ms 296 KB Correct answer: answer = 71923
7 Correct 1 ms 204 KB Correct answer: answer = 77137
8 Correct 1 ms 204 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 1 ms 292 KB Correct answer: answer = 32
12 Correct 1 ms 332 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 0 ms 204 KB Correct answer: answer = 796
16 Correct 2 ms 332 KB Correct answer: answer = 7580
17 Correct 1 ms 332 KB Correct answer: answer = 1904
18 Correct 1 ms 208 KB Correct answer: answer = 996004
19 Correct 1 ms 332 KB Correct answer: answer = 38817
20 Correct 1 ms 204 KB Correct answer: answer = 4096
21 Correct 0 ms 204 KB Correct answer: answer = 1
22 Correct 1 ms 292 KB Correct answer: answer = 1
23 Correct 1 ms 296 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 1 ms 292 KB Correct answer: answer = 4
3 Correct 0 ms 204 KB Correct answer: answer = 4
4 Correct 0 ms 204 KB Correct answer: answer = 12
5 Correct 0 ms 204 KB Correct answer: answer = 52
6 Correct 0 ms 208 KB Correct answer: answer = 210
7 Correct 0 ms 204 KB Correct answer: answer = 88
8 Correct 0 ms 204 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 1 ms 204 KB Correct answer: answer = 49
13 Correct 1 ms 204 KB Correct answer: answer = 151
14 Correct 1 ms 204 KB Correct answer: answer = 7550
15 Correct 0 ms 204 KB Correct answer: answer = 7220
16 Correct 0 ms 204 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 0 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 296 KB Correct answer: answer = 4
23 Correct 0 ms 204 KB Correct answer: answer = 1
24 Correct 0 ms 204 KB Correct answer: answer = 5
25 Correct 0 ms 204 KB Correct answer: answer = 41
26 Correct 0 ms 296 KB Correct answer: answer = 71923
27 Correct 1 ms 204 KB Correct answer: answer = 77137
28 Correct 1 ms 204 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 1 ms 292 KB Correct answer: answer = 32
32 Correct 1 ms 332 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 0 ms 204 KB Correct answer: answer = 796
36 Correct 2 ms 332 KB Correct answer: answer = 7580
37 Correct 1 ms 332 KB Correct answer: answer = 1904
38 Correct 1 ms 208 KB Correct answer: answer = 996004
39 Correct 1 ms 332 KB Correct answer: answer = 38817
40 Correct 1 ms 204 KB Correct answer: answer = 4096
41 Correct 0 ms 204 KB Correct answer: answer = 1
42 Correct 1 ms 292 KB Correct answer: answer = 1
43 Correct 1 ms 296 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 340 KB Correct answer: answer = 9
47 Correct 0 ms 216 KB Correct answer: answer = 9
48 Correct 0 ms 204 KB Correct answer: answer = 21
49 Correct 1 ms 204 KB Correct answer: answer = 71
50 Correct 0 ms 204 KB Correct answer: answer = 77
51 Correct 1 ms 204 KB Correct answer: answer = 400
52 Correct 1 ms 204 KB Correct answer: answer = 996004
53 Correct 1 ms 204 KB Correct answer: answer = 997310
54 Correct 0 ms 204 KB Correct answer: answer = 990781
55 Correct 0 ms 204 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 332 KB Correct answer: answer = 63501
59 Correct 1 ms 332 KB Correct answer: answer = 323501
60 Correct 1 ms 332 KB Correct answer: answer = 752500
61 Correct 1 ms 296 KB Correct answer: answer = 761480
62 Correct 1 ms 204 KB Correct answer: answer = 758932
63 Correct 0 ms 204 KB Correct answer: answer = 1000000
64 Correct 1 ms 332 KB Correct answer: answer = 750500
65 Correct 0 ms 204 KB Correct answer: answer = 1000000
66 Correct 0 ms 204 KB Correct answer: answer = 250000
67 Correct 1 ms 296 KB Correct answer: answer = 250000
68 Correct 1 ms 204 KB Correct answer: answer = 1000000
69 Correct 1 ms 204 KB Correct answer: answer = 994009
70 Correct 1 ms 204 KB Correct answer: answer = 59315
71 Correct 1 ms 204 KB Correct answer: answer = 25454
72 Correct 1 ms 292 KB Correct answer: answer = 1504
73 Correct 0 ms 292 KB Correct answer: answer = 37486
74 Correct 1 ms 204 KB Correct answer: answer = 4284
75 Correct 0 ms 204 KB Correct answer: answer = 158008
76 Correct 1 ms 204 KB Correct answer: answer = 51860
77 Correct 0 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 1 ms 292 KB Correct answer: answer = 4
3 Correct 0 ms 204 KB Correct answer: answer = 4
4 Correct 0 ms 204 KB Correct answer: answer = 12
5 Correct 0 ms 204 KB Correct answer: answer = 52
6 Correct 0 ms 208 KB Correct answer: answer = 210
7 Correct 0 ms 204 KB Correct answer: answer = 88
8 Correct 0 ms 204 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 1 ms 204 KB Correct answer: answer = 49
13 Correct 1 ms 204 KB Correct answer: answer = 151
14 Correct 1 ms 204 KB Correct answer: answer = 7550
15 Correct 0 ms 204 KB Correct answer: answer = 7220
16 Correct 0 ms 204 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 0 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 296 KB Correct answer: answer = 4
23 Correct 0 ms 204 KB Correct answer: answer = 1
24 Correct 0 ms 204 KB Correct answer: answer = 5
25 Correct 0 ms 204 KB Correct answer: answer = 41
26 Correct 0 ms 296 KB Correct answer: answer = 71923
27 Correct 1 ms 204 KB Correct answer: answer = 77137
28 Correct 1 ms 204 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 1 ms 292 KB Correct answer: answer = 32
32 Correct 1 ms 332 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 0 ms 204 KB Correct answer: answer = 796
36 Correct 2 ms 332 KB Correct answer: answer = 7580
37 Correct 1 ms 332 KB Correct answer: answer = 1904
38 Correct 1 ms 208 KB Correct answer: answer = 996004
39 Correct 1 ms 332 KB Correct answer: answer = 38817
40 Correct 1 ms 204 KB Correct answer: answer = 4096
41 Correct 0 ms 204 KB Correct answer: answer = 1
42 Correct 1 ms 292 KB Correct answer: answer = 1
43 Correct 1 ms 296 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 340 KB Correct answer: answer = 9
47 Correct 0 ms 216 KB Correct answer: answer = 9
48 Correct 0 ms 204 KB Correct answer: answer = 21
49 Correct 1 ms 204 KB Correct answer: answer = 71
50 Correct 0 ms 204 KB Correct answer: answer = 77
51 Correct 1 ms 204 KB Correct answer: answer = 400
52 Correct 1 ms 204 KB Correct answer: answer = 996004
53 Correct 1 ms 204 KB Correct answer: answer = 997310
54 Correct 0 ms 204 KB Correct answer: answer = 990781
55 Correct 0 ms 204 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 332 KB Correct answer: answer = 63501
59 Correct 1 ms 332 KB Correct answer: answer = 323501
60 Correct 1 ms 332 KB Correct answer: answer = 752500
61 Correct 1 ms 296 KB Correct answer: answer = 761480
62 Correct 1 ms 204 KB Correct answer: answer = 758932
63 Correct 0 ms 204 KB Correct answer: answer = 1000000
64 Correct 1 ms 332 KB Correct answer: answer = 750500
65 Correct 0 ms 204 KB Correct answer: answer = 1000000
66 Correct 0 ms 204 KB Correct answer: answer = 250000
67 Correct 1 ms 296 KB Correct answer: answer = 250000
68 Correct 1 ms 204 KB Correct answer: answer = 1000000
69 Correct 1 ms 204 KB Correct answer: answer = 994009
70 Correct 1 ms 204 KB Correct answer: answer = 59315
71 Correct 1 ms 204 KB Correct answer: answer = 25454
72 Correct 1 ms 292 KB Correct answer: answer = 1504
73 Correct 0 ms 292 KB Correct answer: answer = 37486
74 Correct 1 ms 204 KB Correct answer: answer = 4284
75 Correct 0 ms 204 KB Correct answer: answer = 158008
76 Correct 1 ms 204 KB Correct answer: answer = 51860
77 Correct 0 ms 204 KB Correct answer: answer = 12985
78 Correct 2 ms 376 KB Correct answer: answer = 997864126212
79 Correct 2 ms 332 KB Correct answer: answer = 998608411647
80 Correct 1 ms 332 KB Correct answer: answer = 995265560477
81 Correct 5 ms 588 KB Correct answer: answer = 10125000
82 Correct 6 ms 588 KB Correct answer: answer = 2291668
83 Correct 3 ms 460 KB Correct answer: answer = 42388
84 Correct 2 ms 460 KB Correct answer: answer = 10318
85 Correct 3 ms 436 KB Correct answer: answer = 3416
86 Correct 10 ms 612 KB Correct answer: answer = 331708193881
87 Correct 11 ms 612 KB Correct answer: answer = 2861193756
88 Correct 10 ms 628 KB Correct answer: answer = 114646930
89 Correct 7 ms 588 KB Correct answer: answer = 9280921
90 Correct 7 ms 588 KB Correct answer: answer = 999984053400
91 Correct 10 ms 556 KB Correct answer: answer = 750935949134
92 Correct 1 ms 432 KB Correct answer: answer = 1000000000000
93 Correct 1 ms 380 KB Correct answer: answer = 998762383161
94 Correct 10 ms 588 KB Correct answer: answer = 23017412908
95 Correct 2 ms 440 KB Correct answer: answer = 728143410622
96 Correct 1 ms 288 KB Correct answer: answer = 2
97 Correct 9 ms 588 KB Correct answer: answer = 1824916
98 Correct 10 ms 640 KB Correct answer: answer = 10680029
99 Correct 7 ms 588 KB Correct answer: answer = 18351700
100 Correct 9 ms 496 KB Correct answer: answer = 16040026
101 Correct 2 ms 332 KB Correct answer: answer = 253968628325
102 Correct 3 ms 436 KB Correct answer: answer = 10267
103 Correct 8 ms 580 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 332 KB Correct answer: answer = 86064128360
108 Correct 3 ms 380 KB Correct answer: answer = 12698259150
109 Correct 6 ms 588 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 1 ms 292 KB Correct answer: answer = 4
3 Correct 0 ms 204 KB Correct answer: answer = 4
4 Correct 0 ms 204 KB Correct answer: answer = 12
5 Correct 0 ms 204 KB Correct answer: answer = 52
6 Correct 0 ms 208 KB Correct answer: answer = 210
7 Correct 0 ms 204 KB Correct answer: answer = 88
8 Correct 0 ms 204 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 1 ms 204 KB Correct answer: answer = 49
13 Correct 1 ms 204 KB Correct answer: answer = 151
14 Correct 1 ms 204 KB Correct answer: answer = 7550
15 Correct 0 ms 204 KB Correct answer: answer = 7220
16 Correct 0 ms 204 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 0 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 296 KB Correct answer: answer = 4
23 Correct 0 ms 204 KB Correct answer: answer = 1
24 Correct 0 ms 204 KB Correct answer: answer = 5
25 Correct 0 ms 204 KB Correct answer: answer = 41
26 Correct 0 ms 296 KB Correct answer: answer = 71923
27 Correct 1 ms 204 KB Correct answer: answer = 77137
28 Correct 1 ms 204 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 1 ms 292 KB Correct answer: answer = 32
32 Correct 1 ms 332 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 0 ms 204 KB Correct answer: answer = 796
36 Correct 2 ms 332 KB Correct answer: answer = 7580
37 Correct 1 ms 332 KB Correct answer: answer = 1904
38 Correct 1 ms 208 KB Correct answer: answer = 996004
39 Correct 1 ms 332 KB Correct answer: answer = 38817
40 Correct 1 ms 204 KB Correct answer: answer = 4096
41 Correct 0 ms 204 KB Correct answer: answer = 1
42 Correct 1 ms 292 KB Correct answer: answer = 1
43 Correct 1 ms 296 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 340 KB Correct answer: answer = 9
47 Correct 0 ms 216 KB Correct answer: answer = 9
48 Correct 0 ms 204 KB Correct answer: answer = 21
49 Correct 1 ms 204 KB Correct answer: answer = 71
50 Correct 0 ms 204 KB Correct answer: answer = 77
51 Correct 1 ms 204 KB Correct answer: answer = 400
52 Correct 1 ms 204 KB Correct answer: answer = 996004
53 Correct 1 ms 204 KB Correct answer: answer = 997310
54 Correct 0 ms 204 KB Correct answer: answer = 990781
55 Correct 0 ms 204 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 332 KB Correct answer: answer = 63501
59 Correct 1 ms 332 KB Correct answer: answer = 323501
60 Correct 1 ms 332 KB Correct answer: answer = 752500
61 Correct 1 ms 296 KB Correct answer: answer = 761480
62 Correct 1 ms 204 KB Correct answer: answer = 758932
63 Correct 0 ms 204 KB Correct answer: answer = 1000000
64 Correct 1 ms 332 KB Correct answer: answer = 750500
65 Correct 0 ms 204 KB Correct answer: answer = 1000000
66 Correct 0 ms 204 KB Correct answer: answer = 250000
67 Correct 1 ms 296 KB Correct answer: answer = 250000
68 Correct 1 ms 204 KB Correct answer: answer = 1000000
69 Correct 1 ms 204 KB Correct answer: answer = 994009
70 Correct 1 ms 204 KB Correct answer: answer = 59315
71 Correct 1 ms 204 KB Correct answer: answer = 25454
72 Correct 1 ms 292 KB Correct answer: answer = 1504
73 Correct 0 ms 292 KB Correct answer: answer = 37486
74 Correct 1 ms 204 KB Correct answer: answer = 4284
75 Correct 0 ms 204 KB Correct answer: answer = 158008
76 Correct 1 ms 204 KB Correct answer: answer = 51860
77 Correct 0 ms 204 KB Correct answer: answer = 12985
78 Correct 2 ms 376 KB Correct answer: answer = 997864126212
79 Correct 2 ms 332 KB Correct answer: answer = 998608411647
80 Correct 1 ms 332 KB Correct answer: answer = 995265560477
81 Correct 5 ms 588 KB Correct answer: answer = 10125000
82 Correct 6 ms 588 KB Correct answer: answer = 2291668
83 Correct 3 ms 460 KB Correct answer: answer = 42388
84 Correct 2 ms 460 KB Correct answer: answer = 10318
85 Correct 3 ms 436 KB Correct answer: answer = 3416
86 Correct 10 ms 612 KB Correct answer: answer = 331708193881
87 Correct 11 ms 612 KB Correct answer: answer = 2861193756
88 Correct 10 ms 628 KB Correct answer: answer = 114646930
89 Correct 7 ms 588 KB Correct answer: answer = 9280921
90 Correct 7 ms 588 KB Correct answer: answer = 999984053400
91 Correct 10 ms 556 KB Correct answer: answer = 750935949134
92 Correct 1 ms 432 KB Correct answer: answer = 1000000000000
93 Correct 1 ms 380 KB Correct answer: answer = 998762383161
94 Correct 10 ms 588 KB Correct answer: answer = 23017412908
95 Correct 2 ms 440 KB Correct answer: answer = 728143410622
96 Correct 1 ms 288 KB Correct answer: answer = 2
97 Correct 9 ms 588 KB Correct answer: answer = 1824916
98 Correct 10 ms 640 KB Correct answer: answer = 10680029
99 Correct 7 ms 588 KB Correct answer: answer = 18351700
100 Correct 9 ms 496 KB Correct answer: answer = 16040026
101 Correct 2 ms 332 KB Correct answer: answer = 253968628325
102 Correct 3 ms 436 KB Correct answer: answer = 10267
103 Correct 8 ms 580 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 332 KB Correct answer: answer = 86064128360
108 Correct 3 ms 380 KB Correct answer: answer = 12698259150
109 Correct 6 ms 588 KB Correct answer: answer = 1185259288
110 Correct 19 ms 2080 KB Correct answer: answer = 999889968863
111 Correct 16 ms 2124 KB Correct answer: answer = 999861384931
112 Correct 16 ms 2076 KB Correct answer: answer = 999811809929
113 Correct 16 ms 2064 KB Correct answer: answer = 999869756441
114 Correct 66 ms 4632 KB Correct answer: answer = 1700000000
115 Correct 75 ms 4752 KB Correct answer: answer = 131666670
116 Correct 21 ms 1736 KB Correct answer: answer = 89478486
117 Correct 23 ms 1740 KB Correct answer: answer = 4971040
118 Correct 31 ms 1844 KB Correct answer: answer = 2711494
119 Correct 76 ms 4952 KB Correct answer: answer = 25252530
120 Correct 71 ms 4916 KB Correct answer: answer = 62500000
121 Correct 119 ms 4440 KB Correct answer: answer = 333175097780
122 Correct 159 ms 4384 KB Correct answer: answer = 33121180179
123 Correct 133 ms 4376 KB Correct answer: answer = 9802314015
124 Correct 73 ms 5004 KB Correct answer: answer = 32567551
125 Correct 85 ms 4876 KB Correct answer: answer = 997525000000
126 Correct 111 ms 4280 KB Correct answer: answer = 752723538884
127 Correct 10 ms 2080 KB Correct answer: answer = 1000000000000
128 Correct 14 ms 2072 KB Correct answer: answer = 999978000121
129 Correct 15 ms 2084 KB Correct answer: answer = 745986144735
130 Correct 11 ms 1680 KB Correct answer: answer = 2
131 Correct 93 ms 4888 KB Correct answer: answer = 277966670
132 Correct 85 ms 4316 KB Correct answer: answer = 2500900082
133 Correct 24 ms 2344 KB Correct answer: answer = 301248349636
134 Correct 50 ms 2436 KB Correct answer: answer = 14118891
135 Correct 15 ms 2084 KB Correct answer: answer = 14384977265
136 Correct 15 ms 2148 KB Correct answer: answer = 3681368330
137 Correct 20 ms 2080 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 1 ms 292 KB Correct answer: answer = 4
3 Correct 0 ms 204 KB Correct answer: answer = 4
4 Correct 0 ms 204 KB Correct answer: answer = 12
5 Correct 0 ms 204 KB Correct answer: answer = 52
6 Correct 0 ms 208 KB Correct answer: answer = 210
7 Correct 0 ms 204 KB Correct answer: answer = 88
8 Correct 0 ms 204 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 1 ms 204 KB Correct answer: answer = 49
13 Correct 1 ms 204 KB Correct answer: answer = 151
14 Correct 1 ms 204 KB Correct answer: answer = 7550
15 Correct 0 ms 204 KB Correct answer: answer = 7220
16 Correct 0 ms 204 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 0 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 296 KB Correct answer: answer = 4
23 Correct 0 ms 204 KB Correct answer: answer = 1
24 Correct 0 ms 204 KB Correct answer: answer = 5
25 Correct 0 ms 204 KB Correct answer: answer = 41
26 Correct 0 ms 296 KB Correct answer: answer = 71923
27 Correct 1 ms 204 KB Correct answer: answer = 77137
28 Correct 1 ms 204 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 1 ms 292 KB Correct answer: answer = 32
32 Correct 1 ms 332 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 0 ms 204 KB Correct answer: answer = 796
36 Correct 2 ms 332 KB Correct answer: answer = 7580
37 Correct 1 ms 332 KB Correct answer: answer = 1904
38 Correct 1 ms 208 KB Correct answer: answer = 996004
39 Correct 1 ms 332 KB Correct answer: answer = 38817
40 Correct 1 ms 204 KB Correct answer: answer = 4096
41 Correct 0 ms 204 KB Correct answer: answer = 1
42 Correct 1 ms 292 KB Correct answer: answer = 1
43 Correct 1 ms 296 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 340 KB Correct answer: answer = 9
47 Correct 0 ms 216 KB Correct answer: answer = 9
48 Correct 0 ms 204 KB Correct answer: answer = 21
49 Correct 1 ms 204 KB Correct answer: answer = 71
50 Correct 0 ms 204 KB Correct answer: answer = 77
51 Correct 1 ms 204 KB Correct answer: answer = 400
52 Correct 1 ms 204 KB Correct answer: answer = 996004
53 Correct 1 ms 204 KB Correct answer: answer = 997310
54 Correct 0 ms 204 KB Correct answer: answer = 990781
55 Correct 0 ms 204 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 332 KB Correct answer: answer = 63501
59 Correct 1 ms 332 KB Correct answer: answer = 323501
60 Correct 1 ms 332 KB Correct answer: answer = 752500
61 Correct 1 ms 296 KB Correct answer: answer = 761480
62 Correct 1 ms 204 KB Correct answer: answer = 758932
63 Correct 0 ms 204 KB Correct answer: answer = 1000000
64 Correct 1 ms 332 KB Correct answer: answer = 750500
65 Correct 0 ms 204 KB Correct answer: answer = 1000000
66 Correct 0 ms 204 KB Correct answer: answer = 250000
67 Correct 1 ms 296 KB Correct answer: answer = 250000
68 Correct 1 ms 204 KB Correct answer: answer = 1000000
69 Correct 1 ms 204 KB Correct answer: answer = 994009
70 Correct 1 ms 204 KB Correct answer: answer = 59315
71 Correct 1 ms 204 KB Correct answer: answer = 25454
72 Correct 1 ms 292 KB Correct answer: answer = 1504
73 Correct 0 ms 292 KB Correct answer: answer = 37486
74 Correct 1 ms 204 KB Correct answer: answer = 4284
75 Correct 0 ms 204 KB Correct answer: answer = 158008
76 Correct 1 ms 204 KB Correct answer: answer = 51860
77 Correct 0 ms 204 KB Correct answer: answer = 12985
78 Correct 2 ms 376 KB Correct answer: answer = 997864126212
79 Correct 2 ms 332 KB Correct answer: answer = 998608411647
80 Correct 1 ms 332 KB Correct answer: answer = 995265560477
81 Correct 5 ms 588 KB Correct answer: answer = 10125000
82 Correct 6 ms 588 KB Correct answer: answer = 2291668
83 Correct 3 ms 460 KB Correct answer: answer = 42388
84 Correct 2 ms 460 KB Correct answer: answer = 10318
85 Correct 3 ms 436 KB Correct answer: answer = 3416
86 Correct 10 ms 612 KB Correct answer: answer = 331708193881
87 Correct 11 ms 612 KB Correct answer: answer = 2861193756
88 Correct 10 ms 628 KB Correct answer: answer = 114646930
89 Correct 7 ms 588 KB Correct answer: answer = 9280921
90 Correct 7 ms 588 KB Correct answer: answer = 999984053400
91 Correct 10 ms 556 KB Correct answer: answer = 750935949134
92 Correct 1 ms 432 KB Correct answer: answer = 1000000000000
93 Correct 1 ms 380 KB Correct answer: answer = 998762383161
94 Correct 10 ms 588 KB Correct answer: answer = 23017412908
95 Correct 2 ms 440 KB Correct answer: answer = 728143410622
96 Correct 1 ms 288 KB Correct answer: answer = 2
97 Correct 9 ms 588 KB Correct answer: answer = 1824916
98 Correct 10 ms 640 KB Correct answer: answer = 10680029
99 Correct 7 ms 588 KB Correct answer: answer = 18351700
100 Correct 9 ms 496 KB Correct answer: answer = 16040026
101 Correct 2 ms 332 KB Correct answer: answer = 253968628325
102 Correct 3 ms 436 KB Correct answer: answer = 10267
103 Correct 8 ms 580 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 332 KB Correct answer: answer = 86064128360
108 Correct 3 ms 380 KB Correct answer: answer = 12698259150
109 Correct 6 ms 588 KB Correct answer: answer = 1185259288
110 Correct 19 ms 2080 KB Correct answer: answer = 999889968863
111 Correct 16 ms 2124 KB Correct answer: answer = 999861384931
112 Correct 16 ms 2076 KB Correct answer: answer = 999811809929
113 Correct 16 ms 2064 KB Correct answer: answer = 999869756441
114 Correct 66 ms 4632 KB Correct answer: answer = 1700000000
115 Correct 75 ms 4752 KB Correct answer: answer = 131666670
116 Correct 21 ms 1736 KB Correct answer: answer = 89478486
117 Correct 23 ms 1740 KB Correct answer: answer = 4971040
118 Correct 31 ms 1844 KB Correct answer: answer = 2711494
119 Correct 76 ms 4952 KB Correct answer: answer = 25252530
120 Correct 71 ms 4916 KB Correct answer: answer = 62500000
121 Correct 119 ms 4440 KB Correct answer: answer = 333175097780
122 Correct 159 ms 4384 KB Correct answer: answer = 33121180179
123 Correct 133 ms 4376 KB Correct answer: answer = 9802314015
124 Correct 73 ms 5004 KB Correct answer: answer = 32567551
125 Correct 85 ms 4876 KB Correct answer: answer = 997525000000
126 Correct 111 ms 4280 KB Correct answer: answer = 752723538884
127 Correct 10 ms 2080 KB Correct answer: answer = 1000000000000
128 Correct 14 ms 2072 KB Correct answer: answer = 999978000121
129 Correct 15 ms 2084 KB Correct answer: answer = 745986144735
130 Correct 11 ms 1680 KB Correct answer: answer = 2
131 Correct 93 ms 4888 KB Correct answer: answer = 277966670
132 Correct 85 ms 4316 KB Correct answer: answer = 2500900082
133 Correct 24 ms 2344 KB Correct answer: answer = 301248349636
134 Correct 50 ms 2436 KB Correct answer: answer = 14118891
135 Correct 15 ms 2084 KB Correct answer: answer = 14384977265
136 Correct 15 ms 2148 KB Correct answer: answer = 3681368330
137 Correct 20 ms 2080 KB Correct answer: answer = 2720316816
138 Correct 30 ms 3908 KB Correct answer: answer = 999976000144
139 Correct 30 ms 3880 KB Correct answer: answer = 999856102410
140 Correct 29 ms 3908 KB Correct answer: answer = 999958401531
141 Correct 30 ms 3876 KB Correct answer: answer = 999769649944
142 Correct 30 ms 3880 KB Correct answer: answer = 999874525918
143 Correct 156 ms 9540 KB Correct answer: answer = 6050000000
144 Correct 168 ms 9416 KB Correct answer: answer = 1112500000
145 Correct 85 ms 6444 KB Correct answer: answer = 4294967296
146 Correct 125 ms 6488 KB Correct answer: answer = 87652406
147 Correct 97 ms 6404 KB Correct answer: answer = 6297664
148 Correct 90 ms 6416 KB Correct answer: answer = 196612
149 Correct 151 ms 9708 KB Correct answer: answer = 15015100
150 Correct 158 ms 9612 KB Correct answer: answer = 25000000
151 Correct 246 ms 8400 KB Correct answer: answer = 333230209550
152 Correct 238 ms 8468 KB Correct answer: answer = 917123769
153 Correct 231 ms 8460 KB Correct answer: answer = 95162
154 Correct 158 ms 9616 KB Correct answer: answer = 382616191
155 Correct 173 ms 9680 KB Correct answer: answer = 990033333400
156 Correct 205 ms 9628 KB Correct answer: answer = 990000100000
157 Correct 200 ms 7888 KB Correct answer: answer = 749998188180
158 Correct 28 ms 3880 KB Correct answer: answer = 1000000000000
159 Correct 26 ms 3912 KB Correct answer: answer = 999988000036
160 Correct 29 ms 3996 KB Correct answer: answer = 744929274393
161 Correct 17 ms 3020 KB Correct answer: answer = 2
162 Correct 208 ms 9508 KB Correct answer: answer = 1300024
163 Correct 155 ms 9728 KB Correct answer: answer = 5000700010
164 Correct 49 ms 4452 KB Correct answer: answer = 354997100800
165 Correct 111 ms 4700 KB Correct answer: answer = 257000
166 Correct 104 ms 5376 KB Correct answer: answer = 3765323
167 Correct 95 ms 5144 KB Correct answer: answer = 1525903
168 Correct 29 ms 3972 KB Correct answer: answer = 67618137730
169 Correct 29 ms 3976 KB Correct answer: answer = 12656680171
170 Correct 34 ms 4008 KB Correct answer: answer = 579831736
171 Correct 82 ms 5196 KB Correct answer: answer = 23605611
172 Correct 34 ms 4140 KB Correct answer: answer = 7052481200
173 Correct 49 ms 4568 KB Correct answer: answer = 1314039500
174 Correct 62 ms 4852 KB Correct answer: answer = 302484000
175 Correct 123 ms 6952 KB Correct answer: answer = 52348480