oj.uz

Submission #492859

# Submission time Handle Problem Language Result Execution time Memory
492859 2021-12-09T11:03:16 Z balbit Aliens (IOI16_aliens) C++14
100 / 100
 887 ms 24256 KB 
#include "aliens.h"
#include <bits/stdc++.h>
//#define int ll
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<ll, ll>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif

const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;


void GG(){cout<<"0\n"; exit(0);}

ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b, ll mo = mod){
    if (b==1) return b;
    return (mo-mo/b) * inv(mo%b,mo) % mo;
}

const int MM = 1e6+5;
const int NN = 1e5+5;
ll reach[MM]; // where does this point reach
ll over[NN]; // overcount for this index

ll dp[NN], take[NN];
ll at[NN], to[NN];

inline ll SQ(ll x) {return x*x;}

bool QTYPE = 0;
struct Line{
    mutable ll m, b, p, id;
    bool operator < (const Line &o) const {
        if (QTYPE) return p < o.p;
        return m < o.m;
    }
};

struct LineContainer : multiset<Line> {
    ll div(ll A, ll B) {
        return A/B - ((A%B) && ((A^B)<0));
    }
    bool isect (iterator x, iterator y) {
        if (y == end()) {
            x->p = inf; return false;
        }
        if (x->m == y->m) {
            x->p = x->b > y->b? inf : -inf;
        }else{
            x->p = div(x->b - y->b, y->m - x->m);
        }
        return x->p >= y->p;
    }

    void add(ll m, ll b, int id) {
        m=-m; b=-b;
        auto z = insert({m,b,0,id}), y = z++, x = y;
        while (isect(y,z)) z = erase(z);
        if (x!=begin() && isect(--x, y)) {
            isect(x, y = erase(y));
        }
        while ((y=x)!=begin() && (--x)->p >= y->p) {
            isect(x, erase(y));
        }
    }

    pii query(ll x) {

        QTYPE = 1;
        auto it = lower_bound({0,0,x,-1});
        ll ret = it->m * x + it->b;
        QTYPE = 0;
        return {-ret, it->id};
    }
};

pii brute(int n,ll pen) { // pen is (positive) penalty for each thing chosen
    LineContainer CV;
    REP(i,n+1) {
        if (i!=n && at[i] > to[i+1]) {
            over[i] = SQ(at[i] - to[i+1]);
        }
        if (i) {
            pii yo = CV.query(at[i]);
            dp[i] = yo.f + pen + SQ(at[i]);
            take[i] = take[yo.s]+1;
            bug(i, dp[i], take[i]);
        }
        CV.add(-2 * to[i+1], SQ(to[i+1]) - over[i] + dp[i], i);
    }
    return pii{dp[n], take[n]};
}



long long take_photos(int n, int m, int k, std::vector<int> ROW, std::vector<int> COL) {

    ll re = 0;
    memset(reach, 0x3f, sizeof reach);
    REP(i,n) {
        int a = ROW[i], b = COL[i];
        if (a > b) swap(a,b);
        MN(reach[b], a);
    }
    int nowdep = (0x3f3f3f3f)-1;
    vector<pii> use;
    for (int i = m-1; i>=0; --i) {
        if (reach[i] < nowdep) {
            nowdep = reach[i];
            use.emplace_back(i, reach[i]);
            bug(i, reach[i]);
        }
    }
    reverse(ALL(use));
    bug (SZ(use));
    at[0] = to[0] = -1;
    REP(i, SZ(use)){
        at[i+1] = use[i].f;
        to[i+1] = use[i].s-1;
    }

    {

        ll l = 0, r = 1e13;
        while (l!=r) {
            ll mid = (l+r)/2;
            pii hi = brute(SZ(use), mid);
            if (hi.s > k) {
                // taking too many! penalize!!!
                l = mid+1;
            }else{
                r = mid;
            }
        }

        bug(l);
        pii go = brute(SZ(use), l);
        ll re = (go.s) * -l - (k-go.s)*l + go.f;

        bug(re, go.f, go.s);
        return re;
    }



}


//signed main(){
//    ll r = take_photos(5, 7, 1, vector<int>{0, 4, 4, 4, 4}, vector<int>{3, 4, 6, 5, 6});
//    cout<<r<<endl;
//}
//




//signed main(){
//
//}

Compilation message

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:131:8: warning: unused variable 're' [-Wunused-variable]
  131 |     ll re = 0;
      |        ^~

Subtask #1
4.0 / 4.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
16.0 / 16.0

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

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8140 KB Correct answer: answer = 4
2 Correct 3 ms 8140 KB Correct answer: answer = 4
3 Correct 4 ms 8140 KB Correct answer: answer = 4
4 Correct 3 ms 8140 KB Correct answer: answer = 12
5 Correct 3 ms 8140 KB Correct answer: answer = 52
6 Correct 3 ms 8140 KB Correct answer: answer = 210
7 Correct 4 ms 8140 KB Correct answer: answer = 88
8 Correct 3 ms 8140 KB Correct answer: answer = 7696
9 Correct 4 ms 8140 KB Correct answer: answer = 1
10 Correct 3 ms 8140 KB Correct answer: answer = 2374
11 Correct 3 ms 8140 KB Correct answer: answer = 9502
12 Correct 3 ms 8140 KB Correct answer: answer = 49
13 Correct 4 ms 8140 KB Correct answer: answer = 151
14 Correct 3 ms 8140 KB Correct answer: answer = 7550
15 Correct 3 ms 8140 KB Correct answer: answer = 7220
16 Correct 4 ms 8140 KB Correct answer: answer = 7550
17 Correct 4 ms 8140 KB Correct answer: answer = 10000
18 Correct 4 ms 8140 KB Correct answer: answer = 10000
19 Correct 3 ms 8140 KB Correct answer: answer = 624
20 Correct 3 ms 8140 KB Correct answer: answer = 10000
21 Correct 3 ms 8140 KB Correct answer: answer = 1
22 Correct 3 ms 8140 KB Correct answer: answer = 4
23 Correct 4 ms 8140 KB Correct answer: answer = 1
24 Correct 4 ms 8140 KB Correct answer: answer = 5
25 Correct 5 ms 8100 KB Correct answer: answer = 41
26 Correct 3 ms 8140 KB Correct answer: answer = 71923
27 Correct 4 ms 8140 KB Correct answer: answer = 77137
28 Correct 6 ms 8140 KB Correct answer: answer = 764
29 Correct 5 ms 8140 KB Correct answer: answer = 250000
30 Correct 5 ms 8140 KB Correct answer: answer = 500
31 Correct 3 ms 8140 KB Correct answer: answer = 32
32 Correct 5 ms 8140 KB Correct answer: answer = 130050
33 Correct 6 ms 8140 KB Correct answer: answer = 5110
34 Correct 4 ms 8140 KB Correct answer: answer = 2626
35 Correct 4 ms 8140 KB Correct answer: answer = 796
36 Correct 7 ms 8140 KB Correct answer: answer = 7580
37 Correct 5 ms 8140 KB Correct answer: answer = 1904
38 Correct 5 ms 8140 KB Correct answer: answer = 996004
39 Correct 5 ms 8140 KB Correct answer: answer = 38817
40 Correct 5 ms 8140 KB Correct answer: answer = 4096
41 Correct 3 ms 8140 KB Correct answer: answer = 1
42 Correct 4 ms 8132 KB Correct answer: answer = 1
43 Correct 6 ms 8140 KB Correct answer: answer = 2040
44 Correct 4 ms 8140 KB Correct answer: answer = 2
45 Correct 5 ms 8140 KB Correct answer: answer = 4
46 Correct 4 ms 8128 KB Correct answer: answer = 9
47 Correct 3 ms 8140 KB Correct answer: answer = 9
48 Correct 4 ms 8140 KB Correct answer: answer = 21
49 Correct 4 ms 8140 KB Correct answer: answer = 71
50 Correct 3 ms 8140 KB Correct answer: answer = 77
51 Correct 4 ms 8140 KB Correct answer: answer = 400
52 Correct 4 ms 8140 KB Correct answer: answer = 996004
53 Correct 4 ms 8140 KB Correct answer: answer = 997310
54 Correct 3 ms 8140 KB Correct answer: answer = 990781
55 Correct 3 ms 8140 KB Correct answer: answer = 996545
56 Correct 4 ms 8140 KB Correct answer: answer = 484
57 Correct 3 ms 8140 KB Correct answer: answer = 484
58 Correct 6 ms 8140 KB Correct answer: answer = 63501
59 Correct 6 ms 8148 KB Correct answer: answer = 323501
60 Correct 6 ms 8140 KB Correct answer: answer = 752500
61 Correct 4 ms 8140 KB Correct answer: answer = 761480
62 Correct 4 ms 8140 KB Correct answer: answer = 758932
63 Correct 3 ms 8140 KB Correct answer: answer = 1000000
64 Correct 5 ms 8140 KB Correct answer: answer = 750500
65 Correct 3 ms 8140 KB Correct answer: answer = 1000000
66 Correct 3 ms 8140 KB Correct answer: answer = 250000
67 Correct 4 ms 8140 KB Correct answer: answer = 250000
68 Correct 3 ms 8140 KB Correct answer: answer = 1000000
69 Correct 4 ms 8140 KB Correct answer: answer = 994009
70 Correct 4 ms 8140 KB Correct answer: answer = 59315
71 Correct 5 ms 8184 KB Correct answer: answer = 25454
72 Correct 5 ms 8140 KB Correct answer: answer = 1504
73 Correct 5 ms 8040 KB Correct answer: answer = 37486
74 Correct 4 ms 8140 KB Correct answer: answer = 4284
75 Correct 4 ms 8140 KB Correct answer: answer = 158008
76 Correct 4 ms 8140 KB Correct answer: answer = 51860
77 Correct 4 ms 8140 KB Correct answer: answer = 12985
78 Correct 5 ms 8140 KB Correct answer: answer = 997864126212
79 Correct 5 ms 8140 KB Correct answer: answer = 998608411647
80 Correct 5 ms 8140 KB Correct answer: answer = 995265560477
81 Correct 21 ms 8532 KB Correct answer: answer = 10125000
82 Correct 24 ms 8524 KB Correct answer: answer = 2291668
83 Correct 14 ms 8396 KB Correct answer: answer = 42388
84 Correct 17 ms 8328 KB Correct answer: answer = 10318
85 Correct 15 ms 8396 KB Correct answer: answer = 3416
86 Correct 23 ms 8396 KB Correct answer: answer = 331708193881
87 Correct 29 ms 8396 KB Correct answer: answer = 2861193756
88 Correct 30 ms 8460 KB Correct answer: answer = 114646930
89 Correct 24 ms 8724 KB Correct answer: answer = 9280921
90 Correct 26 ms 8652 KB Correct answer: answer = 999984053400
91 Correct 28 ms 8472 KB Correct answer: answer = 750935949134
92 Correct 5 ms 8140 KB Correct answer: answer = 1000000000000
93 Correct 5 ms 8140 KB Correct answer: answer = 998762383161
94 Correct 25 ms 8468 KB Correct answer: answer = 23017412908
95 Correct 5 ms 8140 KB Correct answer: answer = 728143410622
96 Correct 4 ms 8140 KB Correct answer: answer = 2
97 Correct 24 ms 8628 KB Correct answer: answer = 1824916
98 Correct 27 ms 8504 KB Correct answer: answer = 10680029
99 Correct 25 ms 8524 KB Correct answer: answer = 18351700
100 Correct 20 ms 8524 KB Correct answer: answer = 16040026
101 Correct 7 ms 8140 KB Correct answer: answer = 253968628325
102 Correct 15 ms 8268 KB Correct answer: answer = 10267
103 Correct 31 ms 8636 KB Correct answer: answer = 2582408
104 Correct 5 ms 8140 KB Correct answer: answer = 78024964781
105 Correct 5 ms 8140 KB Correct answer: answer = 9866346457
106 Correct 7 ms 8140 KB Correct answer: answer = 3327720949
107 Correct 6 ms 8140 KB Correct answer: answer = 86064128360
108 Correct 10 ms 8268 KB Correct answer: answer = 12698259150
109 Correct 27 ms 8536 KB Correct answer: answer = 1185259288
110 Correct 14 ms 8888 KB Correct answer: answer = 999889968863
111 Correct 14 ms 8908 KB Correct answer: answer = 999861384931
112 Correct 14 ms 8908 KB Correct answer: answer = 999811809929
113 Correct 16 ms 8908 KB Correct answer: answer = 999869756441
114 Correct 247 ms 12804 KB Correct answer: answer = 1700000000
115 Correct 355 ms 14908 KB Correct answer: answer = 131666670
116 Correct 95 ms 10176 KB Correct answer: answer = 89478486
117 Correct 110 ms 10516 KB Correct answer: answer = 4971040
118 Correct 106 ms 10552 KB Correct answer: answer = 2711494
119 Correct 375 ms 15552 KB Correct answer: answer = 25252530
120 Correct 394 ms 15308 KB Correct answer: answer = 62500000
121 Correct 241 ms 11968 KB Correct answer: answer = 333175097780
122 Correct 293 ms 11968 KB Correct answer: answer = 33121180179
123 Correct 304 ms 11912 KB Correct answer: answer = 9802314015
124 Correct 412 ms 15932 KB Correct answer: answer = 32567551
125 Correct 392 ms 16032 KB Correct answer: answer = 997525000000
126 Correct 280 ms 12104 KB Correct answer: answer = 752723538884
127 Correct 15 ms 9548 KB Correct answer: answer = 1000000000000
128 Correct 15 ms 9572 KB Correct answer: answer = 999978000121
129 Correct 17 ms 9536 KB Correct answer: answer = 745986144735
130 Correct 11 ms 9092 KB Correct answer: answer = 2
131 Correct 349 ms 15200 KB Correct answer: answer = 277966670
132 Correct 247 ms 14152 KB Correct answer: answer = 2500900082
133 Correct 39 ms 9932 KB Correct answer: answer = 301248349636
134 Correct 181 ms 11040 KB Correct answer: answer = 14118891
135 Correct 17 ms 9548 KB Correct answer: answer = 14384977265
136 Correct 20 ms 9568 KB Correct answer: answer = 3681368330
137 Correct 17 ms 9612 KB Correct answer: answer = 2720316816

Subtask #6
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8140 KB Correct answer: answer = 4
2 Correct 3 ms 8140 KB Correct answer: answer = 4
3 Correct 4 ms 8140 KB Correct answer: answer = 4
4 Correct 3 ms 8140 KB Correct answer: answer = 12
5 Correct 3 ms 8140 KB Correct answer: answer = 52
6 Correct 3 ms 8140 KB Correct answer: answer = 210
7 Correct 4 ms 8140 KB Correct answer: answer = 88
8 Correct 3 ms 8140 KB Correct answer: answer = 7696
9 Correct 4 ms 8140 KB Correct answer: answer = 1
10 Correct 3 ms 8140 KB Correct answer: answer = 2374
11 Correct 3 ms 8140 KB Correct answer: answer = 9502
12 Correct 3 ms 8140 KB Correct answer: answer = 49
13 Correct 4 ms 8140 KB Correct answer: answer = 151
14 Correct 3 ms 8140 KB Correct answer: answer = 7550
15 Correct 3 ms 8140 KB Correct answer: answer = 7220
16 Correct 4 ms 8140 KB Correct answer: answer = 7550
17 Correct 4 ms 8140 KB Correct answer: answer = 10000
18 Correct 4 ms 8140 KB Correct answer: answer = 10000
19 Correct 3 ms 8140 KB Correct answer: answer = 624
20 Correct 3 ms 8140 KB Correct answer: answer = 10000
21 Correct 3 ms 8140 KB Correct answer: answer = 1
22 Correct 3 ms 8140 KB Correct answer: answer = 4
23 Correct 4 ms 8140 KB Correct answer: answer = 1
24 Correct 4 ms 8140 KB Correct answer: answer = 5
25 Correct 5 ms 8100 KB Correct answer: answer = 41
26 Correct 3 ms 8140 KB Correct answer: answer = 71923
27 Correct 4 ms 8140 KB Correct answer: answer = 77137
28 Correct 6 ms 8140 KB Correct answer: answer = 764
29 Correct 5 ms 8140 KB Correct answer: answer = 250000
30 Correct 5 ms 8140 KB Correct answer: answer = 500
31 Correct 3 ms 8140 KB Correct answer: answer = 32
32 Correct 5 ms 8140 KB Correct answer: answer = 130050
33 Correct 6 ms 8140 KB Correct answer: answer = 5110
34 Correct 4 ms 8140 KB Correct answer: answer = 2626
35 Correct 4 ms 8140 KB Correct answer: answer = 796
36 Correct 7 ms 8140 KB Correct answer: answer = 7580
37 Correct 5 ms 8140 KB Correct answer: answer = 1904
38 Correct 5 ms 8140 KB Correct answer: answer = 996004
39 Correct 5 ms 8140 KB Correct answer: answer = 38817
40 Correct 5 ms 8140 KB Correct answer: answer = 4096
41 Correct 3 ms 8140 KB Correct answer: answer = 1
42 Correct 4 ms 8132 KB Correct answer: answer = 1
43 Correct 6 ms 8140 KB Correct answer: answer = 2040
44 Correct 4 ms 8140 KB Correct answer: answer = 2
45 Correct 5 ms 8140 KB Correct answer: answer = 4
46 Correct 4 ms 8128 KB Correct answer: answer = 9
47 Correct 3 ms 8140 KB Correct answer: answer = 9
48 Correct 4 ms 8140 KB Correct answer: answer = 21
49 Correct 4 ms 8140 KB Correct answer: answer = 71
50 Correct 3 ms 8140 KB Correct answer: answer = 77
51 Correct 4 ms 8140 KB Correct answer: answer = 400
52 Correct 4 ms 8140 KB Correct answer: answer = 996004
53 Correct 4 ms 8140 KB Correct answer: answer = 997310
54 Correct 3 ms 8140 KB Correct answer: answer = 990781
55 Correct 3 ms 8140 KB Correct answer: answer = 996545
56 Correct 4 ms 8140 KB Correct answer: answer = 484
57 Correct 3 ms 8140 KB Correct answer: answer = 484
58 Correct 6 ms 8140 KB Correct answer: answer = 63501
59 Correct 6 ms 8148 KB Correct answer: answer = 323501
60 Correct 6 ms 8140 KB Correct answer: answer = 752500
61 Correct 4 ms 8140 KB Correct answer: answer = 761480
62 Correct 4 ms 8140 KB Correct answer: answer = 758932
63 Correct 3 ms 8140 KB Correct answer: answer = 1000000
64 Correct 5 ms 8140 KB Correct answer: answer = 750500
65 Correct 3 ms 8140 KB Correct answer: answer = 1000000
66 Correct 3 ms 8140 KB Correct answer: answer = 250000
67 Correct 4 ms 8140 KB Correct answer: answer = 250000
68 Correct 3 ms 8140 KB Correct answer: answer = 1000000
69 Correct 4 ms 8140 KB Correct answer: answer = 994009
70 Correct 4 ms 8140 KB Correct answer: answer = 59315
71 Correct 5 ms 8184 KB Correct answer: answer = 25454
72 Correct 5 ms 8140 KB Correct answer: answer = 1504
73 Correct 5 ms 8040 KB Correct answer: answer = 37486
74 Correct 4 ms 8140 KB Correct answer: answer = 4284
75 Correct 4 ms 8140 KB Correct answer: answer = 158008
76 Correct 4 ms 8140 KB Correct answer: answer = 51860
77 Correct 4 ms 8140 KB Correct answer: answer = 12985
78 Correct 5 ms 8140 KB Correct answer: answer = 997864126212
79 Correct 5 ms 8140 KB Correct answer: answer = 998608411647
80 Correct 5 ms 8140 KB Correct answer: answer = 995265560477
81 Correct 21 ms 8532 KB Correct answer: answer = 10125000
82 Correct 24 ms 8524 KB Correct answer: answer = 2291668
83 Correct 14 ms 8396 KB Correct answer: answer = 42388
84 Correct 17 ms 8328 KB Correct answer: answer = 10318
85 Correct 15 ms 8396 KB Correct answer: answer = 3416
86 Correct 23 ms 8396 KB Correct answer: answer = 331708193881
87 Correct 29 ms 8396 KB Correct answer: answer = 2861193756
88 Correct 30 ms 8460 KB Correct answer: answer = 114646930
89 Correct 24 ms 8724 KB Correct answer: answer = 9280921
90 Correct 26 ms 8652 KB Correct answer: answer = 999984053400
91 Correct 28 ms 8472 KB Correct answer: answer = 750935949134
92 Correct 5 ms 8140 KB Correct answer: answer = 1000000000000
93 Correct 5 ms 8140 KB Correct answer: answer = 998762383161
94 Correct 25 ms 8468 KB Correct answer: answer = 23017412908
95 Correct 5 ms 8140 KB Correct answer: answer = 728143410622
96 Correct 4 ms 8140 KB Correct answer: answer = 2
97 Correct 24 ms 8628 KB Correct answer: answer = 1824916
98 Correct 27 ms 8504 KB Correct answer: answer = 10680029
99 Correct 25 ms 8524 KB Correct answer: answer = 18351700
100 Correct 20 ms 8524 KB Correct answer: answer = 16040026
101 Correct 7 ms 8140 KB Correct answer: answer = 253968628325
102 Correct 15 ms 8268 KB Correct answer: answer = 10267
103 Correct 31 ms 8636 KB Correct answer: answer = 2582408
104 Correct 5 ms 8140 KB Correct answer: answer = 78024964781
105 Correct 5 ms 8140 KB Correct answer: answer = 9866346457
106 Correct 7 ms 8140 KB Correct answer: answer = 3327720949
107 Correct 6 ms 8140 KB Correct answer: answer = 86064128360
108 Correct 10 ms 8268 KB Correct answer: answer = 12698259150
109 Correct 27 ms 8536 KB Correct answer: answer = 1185259288
110 Correct 14 ms 8888 KB Correct answer: answer = 999889968863
111 Correct 14 ms 8908 KB Correct answer: answer = 999861384931
112 Correct 14 ms 8908 KB Correct answer: answer = 999811809929
113 Correct 16 ms 8908 KB Correct answer: answer = 999869756441
114 Correct 247 ms 12804 KB Correct answer: answer = 1700000000
115 Correct 355 ms 14908 KB Correct answer: answer = 131666670
116 Correct 95 ms 10176 KB Correct answer: answer = 89478486
117 Correct 110 ms 10516 KB Correct answer: answer = 4971040
118 Correct 106 ms 10552 KB Correct answer: answer = 2711494
119 Correct 375 ms 15552 KB Correct answer: answer = 25252530
120 Correct 394 ms 15308 KB Correct answer: answer = 62500000
121 Correct 241 ms 11968 KB Correct answer: answer = 333175097780
122 Correct 293 ms 11968 KB Correct answer: answer = 33121180179
123 Correct 304 ms 11912 KB Correct answer: answer = 9802314015
124 Correct 412 ms 15932 KB Correct answer: answer = 32567551
125 Correct 392 ms 16032 KB Correct answer: answer = 997525000000
126 Correct 280 ms 12104 KB Correct answer: answer = 752723538884
127 Correct 15 ms 9548 KB Correct answer: answer = 1000000000000
128 Correct 15 ms 9572 KB Correct answer: answer = 999978000121
129 Correct 17 ms 9536 KB Correct answer: answer = 745986144735
130 Correct 11 ms 9092 KB Correct answer: answer = 2
131 Correct 349 ms 15200 KB Correct answer: answer = 277966670
132 Correct 247 ms 14152 KB Correct answer: answer = 2500900082
133 Correct 39 ms 9932 KB Correct answer: answer = 301248349636
134 Correct 181 ms 11040 KB Correct answer: answer = 14118891
135 Correct 17 ms 9548 KB Correct answer: answer = 14384977265
136 Correct 20 ms 9568 KB Correct answer: answer = 3681368330
137 Correct 17 ms 9612 KB Correct answer: answer = 2720316816
138 Correct 24 ms 11012 KB Correct answer: answer = 999976000144
139 Correct 26 ms 11008 KB Correct answer: answer = 999856102410
140 Correct 34 ms 11048 KB Correct answer: answer = 999958401531
141 Correct 25 ms 10956 KB Correct answer: answer = 999769649944
142 Correct 24 ms 11052 KB Correct answer: answer = 999874525918
143 Correct 598 ms 19148 KB Correct answer: answer = 6050000000
144 Correct 750 ms 21024 KB Correct answer: answer = 1112500000
145 Correct 364 ms 15564 KB Correct answer: answer = 4294967296
146 Correct 545 ms 17692 KB Correct answer: answer = 87652406
147 Correct 553 ms 18232 KB Correct answer: answer = 6297664
148 Correct 534 ms 18132 KB Correct answer: answer = 196612
149 Correct 877 ms 23220 KB Correct answer: answer = 15015100
150 Correct 880 ms 23248 KB Correct answer: answer = 25000000
151 Correct 464 ms 15544 KB Correct answer: answer = 333230209550
152 Correct 708 ms 16032 KB Correct answer: answer = 917123769
153 Correct 751 ms 23076 KB Correct answer: answer = 95162
154 Correct 841 ms 23636 KB Correct answer: answer = 382616191
155 Correct 864 ms 24120 KB Correct answer: answer = 990033333400
156 Correct 887 ms 24256 KB Correct answer: answer = 990000100000
157 Correct 624 ms 20764 KB Correct answer: answer = 749998188180
158 Correct 21 ms 10956 KB Correct answer: answer = 1000000000000
159 Correct 27 ms 10932 KB Correct answer: answer = 999988000036
160 Correct 25 ms 11076 KB Correct answer: answer = 744929274393
161 Correct 20 ms 10060 KB Correct answer: answer = 2
162 Correct 865 ms 24172 KB Correct answer: answer = 1300024
163 Correct 651 ms 20532 KB Correct answer: answer = 5000700010
164 Correct 72 ms 11712 KB Correct answer: answer = 354997100800
165 Correct 390 ms 14828 KB Correct answer: answer = 257000
166 Correct 450 ms 15676 KB Correct answer: answer = 3765323
167 Correct 437 ms 15700 KB Correct answer: answer = 1525903
168 Correct 24 ms 11056 KB Correct answer: answer = 67618137730
169 Correct 25 ms 11032 KB Correct answer: answer = 12656680171
170 Correct 37 ms 11212 KB Correct answer: answer = 579831736
171 Correct 207 ms 13732 KB Correct answer: answer = 23605611
172 Correct 47 ms 11584 KB Correct answer: answer = 7052481200
173 Correct 100 ms 12644 KB Correct answer: answer = 1314039500
174 Correct 168 ms 13696 KB Correct answer: answer = 302484000
175 Correct 464 ms 15828 KB Correct answer: answer = 52348480