oj.uz

Submission #534598

# Submission time Handle Problem Language Result Execution time Memory
534598 2022-03-08T11:22:08 Z David_M Aliens (IOI16_aliens) C++14
100 / 100
 297 ms 11928 KB 
//#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(x) (x).begin(), (x).end()
#define F first
#define S second


deque<pair<pll, int> > dq;
int o=0;

bool check (ll k, ll b){
    int e=dq.size();
    auto [k0,b0]=dq[e-1].F;
    auto [k1,b1]=dq[e-2].F;

//    k1 * x + b1 = k0 * x + b0
//    (b0 - b1) / (k1 - k0)
//    k1 * x + b1 = k * x + b
//    (b - b1) / (k1 - k)
//
//    k < k0 < k1
//
//    (b - b1) / (k1 - k) > (b0 - b1) / (k1 - k0)
//    (b - b1) * (k1 - k0) - (b0 - b1) * (k1 - k) > 0

    return (b - b1) * (k1 - k0) - (b0 - b1) * (k1 - k) < 0;
}

void add(ll k, ll b, int cnt){
    while(dq.size()>1 && check(k, b))dq.pop_back();
    dq.push_back({{k,b},cnt});
}

pll get(int i, ll x, ll C){
    if(i==dq.size()){
        return {100000000000009, 100000000000009};
    }
    auto [k,b]=dq[i].F;
//    cout<<"[i, k, b, x]: "<<i<<" "<<dq.size()<<" "<<k<<" "<<b<<" "<<x<<endl;
    return {k*x+b, dq[i].S};
}

void calc_dp(int n, vector<pll> v, vector<pll> &dp, ll C){
        dp[0]={0,0};
        add(v[0].F*-2, v[0].F*v[0].F, 0);
        for (int i=1; i<=n; i++){
            auto &[ans, cnt]=dp[i];
            ll r=v[i-1].S;
            ans=r*r+C;
//            cout<<"[ans]: "<<ans<<endl;
            cnt=1;
            ll x=r;
            o=min((int)dq.size()-1, o);
            while(i>1 && get(o,x,C)>get(o+1,x,C)){
//                cout<<"[get]: "<<get(o,x,C).F<<" "<<get(o,x,C).S<<endl;
//                cout<<"[get]: "<<get(o+1,x,C).F<<" "<<get(o+1,x,C).S<<endl;
                o++;
            }

            auto [ans0, cnt0]=get(o,x,C);
//            cout<<"[o]: "<<o<<" "<<dq.size()<<" "<<ans0<<" "<<cnt0<<endl;
            ans+=ans0;
            cnt+=cnt0;
            ll s=v[i-1].F;
//            if(i>1 && v[i-2].S>s)s=v[i-2].S;
            dp[i]=min(dp[i], {dp[i-1].F+(r-s)*(r-s)+C, dp[i-1].S+1});
//            cout<<"[i, ans, cnt, C]: "<<i<<" "<<ans<<" "<<cnt<<" "<<C<<endl;

            if(i==n)continue;

            ll l=v[i].F;
            add(-2*l, ans + l*l - max((ll)0, r-l)*max((ll)0, r-l), cnt);

//    dp + (r1-l)^2 - (r2-l)^2
//    dp + r1*r1 + l*l - 2*r1*l - (r2-l)^2
//    (-2*l) * r1 + (dp - l*l + (r-l)^2)

        }
//        for (auto [x, y]:dp){
//            cout<<"[dp]: "<<x<<" "<<y<<endl;
//        }
}


ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
    ll Ans=0;
    vector<pll> v, V(n);

    for (int i=0; i<n; i++){
        if(c[i]<r[i])swap(r[i], c[i]);
        V[i]={r[i], -c[i]};
    }

    sort(all(V));
    ll rr=-1;
    for (auto [l,r]:V){
        r*=-1;
//        cout<<r<<endl;
        if(r>rr)v.pb({l,r+1});
        rr=max(r, rr);
    }
    V.clear();
    n=v.size();

//    for (auto [l,r]:v){
//        cout<<"[l, r]: "<<l<<" "<<r<<endl;
//    }

    ll L=0, R=1ll*m*m;
//    L=49, R=49;
    while(L<=R){
        ll C=(L+R)>>1;
        vector<pll> dp(n+1);
        calc_dp(n, v, dp, C);
//        cout<<"[C,K]: "<<C<<" "<<dp[n].S<<endl;
        if(dp[n].S>k){
            L=C+1;
        }else{
            Ans=dp[n].F;
//            cout<<"[C, Ans]: "<<C<<" "<<Ans<<endl;
            R=C-1;
        }
        dq.clear();
        o=0;
    }

//        cout<<Ans<<" "<<Ans-L*k<<" "<<R<<" "<<L<<endl;
    return Ans-L*k;
}

Compilation message

aliens.cpp: In function 'bool check(long long int, long long int)':
aliens.cpp:18:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   18 |     auto [k0,b0]=dq[e-1].F;
      |          ^
aliens.cpp:19:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   19 |     auto [k1,b1]=dq[e-2].F;
      |          ^
aliens.cpp: In function 'std::pair<long long int, long long int> get(int, long long int, long long int)':
aliens.cpp:40:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<std::pair<std::pair<long long int, long long int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     if(i==dq.size()){
      |        ~^~~~~~~~~~~
aliens.cpp:43:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   43 |     auto [k,b]=dq[i].F;
      |          ^
aliens.cpp: In function 'void calc_dp(int, std::vector<std::pair<long long int, long long int> >, std::vector<std::pair<long long int, long long int> >&, long long int)':
aliens.cpp:52:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   52 |             auto &[ans, cnt]=dp[i];
      |                   ^
aliens.cpp:65:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   65 |             auto [ans0, cnt0]=get(o,x,C);
      |                  ^
aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:101:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  101 |     for (auto [l,r]:V){
      |               ^

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Correct answer: answer = 4
2 Correct 0 ms 204 KB Correct answer: answer = 4
3 Correct 1 ms 204 KB Correct answer: answer = 4
4 Correct 1 ms 204 KB Correct answer: answer = 12
5 Correct 0 ms 204 KB Correct answer: answer = 52
6 Correct 0 ms 204 KB Correct answer: answer = 210
7 Correct 0 ms 204 KB Correct answer: answer = 88
8 Correct 1 ms 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 0 ms 204 KB Correct answer: answer = 9502
12 Correct 1 ms 204 KB Correct answer: answer = 49
13 Correct 0 ms 204 KB Correct answer: answer = 151
14 Correct 1 ms 204 KB Correct answer: answer = 7550
15 Correct 1 ms 204 KB Correct answer: answer = 7220
16 Correct 1 ms 204 KB Correct answer: answer = 7550
17 Correct 1 ms 204 KB Correct answer: answer = 10000
18 Correct 0 ms 204 KB Correct answer: answer = 10000
19 Correct 1 ms 204 KB Correct answer: answer = 624
20 Correct 1 ms 204 KB Correct answer: answer = 10000

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Correct answer: answer = 1
2 Correct 0 ms 204 KB Correct answer: answer = 4
3 Correct 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 204 KB Correct answer: answer = 71923
7 Correct 1 ms 204 KB Correct answer: answer = 77137
8 Correct 2 ms 332 KB Correct answer: answer = 764
9 Correct 1 ms 332 KB Correct answer: answer = 250000
10 Correct 1 ms 332 KB Correct answer: answer = 500
11 Correct 1 ms 204 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 1 ms 204 KB Correct answer: answer = 796
16 Correct 1 ms 332 KB Correct answer: answer = 7580
17 Correct 1 ms 332 KB Correct answer: answer = 1904
18 Correct 1 ms 204 KB Correct answer: answer = 996004
19 Correct 1 ms 204 KB Correct answer: answer = 38817
20 Correct 1 ms 332 KB Correct answer: answer = 4096
21 Correct 0 ms 204 KB Correct answer: answer = 1
22 Correct 1 ms 204 KB Correct answer: answer = 1
23 Correct 1 ms 332 KB Correct answer: answer = 2040
24 Correct 1 ms 204 KB Correct answer: answer = 2

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Correct answer: answer = 4
2 Correct 0 ms 204 KB Correct answer: answer = 4
3 Correct 1 ms 204 KB Correct answer: answer = 4
4 Correct 1 ms 204 KB Correct answer: answer = 12
5 Correct 0 ms 204 KB Correct answer: answer = 52
6 Correct 0 ms 204 KB Correct answer: answer = 210
7 Correct 0 ms 204 KB Correct answer: answer = 88
8 Correct 1 ms 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 0 ms 204 KB Correct answer: answer = 9502
12 Correct 1 ms 204 KB Correct answer: answer = 49
13 Correct 0 ms 204 KB Correct answer: answer = 151
14 Correct 1 ms 204 KB Correct answer: answer = 7550
15 Correct 1 ms 204 KB Correct answer: answer = 7220
16 Correct 1 ms 204 KB Correct answer: answer = 7550
17 Correct 1 ms 204 KB Correct answer: answer = 10000
18 Correct 0 ms 204 KB Correct answer: answer = 10000
19 Correct 1 ms 204 KB Correct answer: answer = 624
20 Correct 1 ms 204 KB Correct answer: answer = 10000
21 Correct 0 ms 204 KB Correct answer: answer = 1
22 Correct 0 ms 204 KB Correct answer: answer = 4
23 Correct 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 204 KB Correct answer: answer = 71923
27 Correct 1 ms 204 KB Correct answer: answer = 77137
28 Correct 2 ms 332 KB Correct answer: answer = 764
29 Correct 1 ms 332 KB Correct answer: answer = 250000
30 Correct 1 ms 332 KB Correct answer: answer = 500
31 Correct 1 ms 204 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 1 ms 204 KB Correct answer: answer = 796
36 Correct 1 ms 332 KB Correct answer: answer = 7580
37 Correct 1 ms 332 KB Correct answer: answer = 1904
38 Correct 1 ms 204 KB Correct answer: answer = 996004
39 Correct 1 ms 204 KB Correct answer: answer = 38817
40 Correct 1 ms 332 KB Correct answer: answer = 4096
41 Correct 0 ms 204 KB Correct answer: answer = 1
42 Correct 1 ms 204 KB Correct answer: answer = 1
43 Correct 1 ms 332 KB Correct answer: answer = 2040
44 Correct 1 ms 204 KB Correct answer: answer = 2
45 Correct 0 ms 204 KB Correct answer: answer = 4
46 Correct 0 ms 204 KB Correct answer: answer = 9
47 Correct 0 ms 204 KB Correct answer: answer = 9
48 Correct 0 ms 204 KB Correct answer: answer = 21
49 Correct 0 ms 204 KB Correct answer: answer = 71
50 Correct 1 ms 204 KB Correct answer: answer = 77
51 Correct 1 ms 204 KB Correct answer: answer = 400
52 Correct 1 ms 204 KB Correct answer: answer = 996004
53 Correct 1 ms 204 KB Correct answer: answer = 997310
54 Correct 1 ms 204 KB Correct answer: answer = 990781
55 Correct 1 ms 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 204 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 1 ms 204 KB Correct answer: answer = 1000000
66 Correct 0 ms 204 KB Correct answer: answer = 250000
67 Correct 1 ms 204 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 332 KB Correct answer: answer = 1504
73 Correct 1 ms 204 KB Correct answer: answer = 37486
74 Correct 1 ms 320 KB Correct answer: answer = 4284
75 Correct 1 ms 204 KB Correct answer: answer = 158008
76 Correct 1 ms 204 KB Correct answer: answer = 51860
77 Correct 1 ms 204 KB Correct answer: answer = 12985

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Correct answer: answer = 4
2 Correct 0 ms 204 KB Correct answer: answer = 4
3 Correct 1 ms 204 KB Correct answer: answer = 4
4 Correct 1 ms 204 KB Correct answer: answer = 12
5 Correct 0 ms 204 KB Correct answer: answer = 52
6 Correct 0 ms 204 KB Correct answer: answer = 210
7 Correct 0 ms 204 KB Correct answer: answer = 88
8 Correct 1 ms 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 0 ms 204 KB Correct answer: answer = 9502
12 Correct 1 ms 204 KB Correct answer: answer = 49
13 Correct 0 ms 204 KB Correct answer: answer = 151
14 Correct 1 ms 204 KB Correct answer: answer = 7550
15 Correct 1 ms 204 KB Correct answer: answer = 7220
16 Correct 1 ms 204 KB Correct answer: answer = 7550
17 Correct 1 ms 204 KB Correct answer: answer = 10000
18 Correct 0 ms 204 KB Correct answer: answer = 10000
19 Correct 1 ms 204 KB Correct answer: answer = 624
20 Correct 1 ms 204 KB Correct answer: answer = 10000
21 Correct 0 ms 204 KB Correct answer: answer = 1
22 Correct 0 ms 204 KB Correct answer: answer = 4
23 Correct 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 204 KB Correct answer: answer = 71923
27 Correct 1 ms 204 KB Correct answer: answer = 77137
28 Correct 2 ms 332 KB Correct answer: answer = 764
29 Correct 1 ms 332 KB Correct answer: answer = 250000
30 Correct 1 ms 332 KB Correct answer: answer = 500
31 Correct 1 ms 204 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 1 ms 204 KB Correct answer: answer = 796
36 Correct 1 ms 332 KB Correct answer: answer = 7580
37 Correct 1 ms 332 KB Correct answer: answer = 1904
38 Correct 1 ms 204 KB Correct answer: answer = 996004
39 Correct 1 ms 204 KB Correct answer: answer = 38817
40 Correct 1 ms 332 KB Correct answer: answer = 4096
41 Correct 0 ms 204 KB Correct answer: answer = 1
42 Correct 1 ms 204 KB Correct answer: answer = 1
43 Correct 1 ms 332 KB Correct answer: answer = 2040
44 Correct 1 ms 204 KB Correct answer: answer = 2
45 Correct 0 ms 204 KB Correct answer: answer = 4
46 Correct 0 ms 204 KB Correct answer: answer = 9
47 Correct 0 ms 204 KB Correct answer: answer = 9
48 Correct 0 ms 204 KB Correct answer: answer = 21
49 Correct 0 ms 204 KB Correct answer: answer = 71
50 Correct 1 ms 204 KB Correct answer: answer = 77
51 Correct 1 ms 204 KB Correct answer: answer = 400
52 Correct 1 ms 204 KB Correct answer: answer = 996004
53 Correct 1 ms 204 KB Correct answer: answer = 997310
54 Correct 1 ms 204 KB Correct answer: answer = 990781
55 Correct 1 ms 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 204 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 1 ms 204 KB Correct answer: answer = 1000000
66 Correct 0 ms 204 KB Correct answer: answer = 250000
67 Correct 1 ms 204 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 332 KB Correct answer: answer = 1504
73 Correct 1 ms 204 KB Correct answer: answer = 37486
74 Correct 1 ms 320 KB Correct answer: answer = 4284
75 Correct 1 ms 204 KB Correct answer: answer = 158008
76 Correct 1 ms 204 KB Correct answer: answer = 51860
77 Correct 1 ms 204 KB Correct answer: answer = 12985
78 Correct 2 ms 332 KB Correct answer: answer = 997864126212
79 Correct 2 ms 408 KB Correct answer: answer = 998608411647
80 Correct 2 ms 460 KB Correct answer: answer = 995265560477
81 Correct 6 ms 588 KB Correct answer: answer = 10125000
82 Correct 8 ms 588 KB Correct answer: answer = 2291668
83 Correct 4 ms 460 KB Correct answer: answer = 42388
84 Correct 4 ms 460 KB Correct answer: answer = 10318
85 Correct 4 ms 436 KB Correct answer: answer = 3416
86 Correct 12 ms 688 KB Correct answer: answer = 331708193881
87 Correct 12 ms 688 KB Correct answer: answer = 2861193756
88 Correct 12 ms 724 KB Correct answer: answer = 114646930
89 Correct 7 ms 716 KB Correct answer: answer = 9280921
90 Correct 9 ms 732 KB Correct answer: answer = 999984053400
91 Correct 11 ms 588 KB Correct answer: answer = 750935949134
92 Correct 2 ms 368 KB Correct answer: answer = 1000000000000
93 Correct 2 ms 432 KB Correct answer: answer = 998762383161
94 Correct 11 ms 556 KB Correct answer: answer = 23017412908
95 Correct 2 ms 432 KB Correct answer: answer = 728143410622
96 Correct 2 ms 332 KB Correct answer: answer = 2
97 Correct 11 ms 712 KB Correct answer: answer = 1824916
98 Correct 10 ms 604 KB Correct answer: answer = 10680029
99 Correct 11 ms 716 KB Correct answer: answer = 18351700
100 Correct 9 ms 688 KB Correct answer: answer = 16040026
101 Correct 3 ms 460 KB Correct answer: answer = 253968628325
102 Correct 4 ms 424 KB Correct answer: answer = 10267
103 Correct 10 ms 736 KB Correct answer: answer = 2582408
104 Correct 2 ms 376 KB Correct answer: answer = 78024964781
105 Correct 2 ms 460 KB Correct answer: answer = 9866346457
106 Correct 3 ms 460 KB Correct answer: answer = 3327720949
107 Correct 3 ms 436 KB Correct answer: answer = 86064128360
108 Correct 3 ms 460 KB Correct answer: answer = 12698259150
109 Correct 9 ms 604 KB Correct answer: answer = 1185259288

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Correct answer: answer = 4
2 Correct 0 ms 204 KB Correct answer: answer = 4
3 Correct 1 ms 204 KB Correct answer: answer = 4
4 Correct 1 ms 204 KB Correct answer: answer = 12
5 Correct 0 ms 204 KB Correct answer: answer = 52
6 Correct 0 ms 204 KB Correct answer: answer = 210
7 Correct 0 ms 204 KB Correct answer: answer = 88
8 Correct 1 ms 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 0 ms 204 KB Correct answer: answer = 9502
12 Correct 1 ms 204 KB Correct answer: answer = 49
13 Correct 0 ms 204 KB Correct answer: answer = 151
14 Correct 1 ms 204 KB Correct answer: answer = 7550
15 Correct 1 ms 204 KB Correct answer: answer = 7220
16 Correct 1 ms 204 KB Correct answer: answer = 7550
17 Correct 1 ms 204 KB Correct answer: answer = 10000
18 Correct 0 ms 204 KB Correct answer: answer = 10000
19 Correct 1 ms 204 KB Correct answer: answer = 624
20 Correct 1 ms 204 KB Correct answer: answer = 10000
21 Correct 0 ms 204 KB Correct answer: answer = 1
22 Correct 0 ms 204 KB Correct answer: answer = 4
23 Correct 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 204 KB Correct answer: answer = 71923
27 Correct 1 ms 204 KB Correct answer: answer = 77137
28 Correct 2 ms 332 KB Correct answer: answer = 764
29 Correct 1 ms 332 KB Correct answer: answer = 250000
30 Correct 1 ms 332 KB Correct answer: answer = 500
31 Correct 1 ms 204 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 1 ms 204 KB Correct answer: answer = 796
36 Correct 1 ms 332 KB Correct answer: answer = 7580
37 Correct 1 ms 332 KB Correct answer: answer = 1904
38 Correct 1 ms 204 KB Correct answer: answer = 996004
39 Correct 1 ms 204 KB Correct answer: answer = 38817
40 Correct 1 ms 332 KB Correct answer: answer = 4096
41 Correct 0 ms 204 KB Correct answer: answer = 1
42 Correct 1 ms 204 KB Correct answer: answer = 1
43 Correct 1 ms 332 KB Correct answer: answer = 2040
44 Correct 1 ms 204 KB Correct answer: answer = 2
45 Correct 0 ms 204 KB Correct answer: answer = 4
46 Correct 0 ms 204 KB Correct answer: answer = 9
47 Correct 0 ms 204 KB Correct answer: answer = 9
48 Correct 0 ms 204 KB Correct answer: answer = 21
49 Correct 0 ms 204 KB Correct answer: answer = 71
50 Correct 1 ms 204 KB Correct answer: answer = 77
51 Correct 1 ms 204 KB Correct answer: answer = 400
52 Correct 1 ms 204 KB Correct answer: answer = 996004
53 Correct 1 ms 204 KB Correct answer: answer = 997310
54 Correct 1 ms 204 KB Correct answer: answer = 990781
55 Correct 1 ms 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 204 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 1 ms 204 KB Correct answer: answer = 1000000
66 Correct 0 ms 204 KB Correct answer: answer = 250000
67 Correct 1 ms 204 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 332 KB Correct answer: answer = 1504
73 Correct 1 ms 204 KB Correct answer: answer = 37486
74 Correct 1 ms 320 KB Correct answer: answer = 4284
75 Correct 1 ms 204 KB Correct answer: answer = 158008
76 Correct 1 ms 204 KB Correct answer: answer = 51860
77 Correct 1 ms 204 KB Correct answer: answer = 12985
78 Correct 2 ms 332 KB Correct answer: answer = 997864126212
79 Correct 2 ms 408 KB Correct answer: answer = 998608411647
80 Correct 2 ms 460 KB Correct answer: answer = 995265560477
81 Correct 6 ms 588 KB Correct answer: answer = 10125000
82 Correct 8 ms 588 KB Correct answer: answer = 2291668
83 Correct 4 ms 460 KB Correct answer: answer = 42388
84 Correct 4 ms 460 KB Correct answer: answer = 10318
85 Correct 4 ms 436 KB Correct answer: answer = 3416
86 Correct 12 ms 688 KB Correct answer: answer = 331708193881
87 Correct 12 ms 688 KB Correct answer: answer = 2861193756
88 Correct 12 ms 724 KB Correct answer: answer = 114646930
89 Correct 7 ms 716 KB Correct answer: answer = 9280921
90 Correct 9 ms 732 KB Correct answer: answer = 999984053400
91 Correct 11 ms 588 KB Correct answer: answer = 750935949134
92 Correct 2 ms 368 KB Correct answer: answer = 1000000000000
93 Correct 2 ms 432 KB Correct answer: answer = 998762383161
94 Correct 11 ms 556 KB Correct answer: answer = 23017412908
95 Correct 2 ms 432 KB Correct answer: answer = 728143410622
96 Correct 2 ms 332 KB Correct answer: answer = 2
97 Correct 11 ms 712 KB Correct answer: answer = 1824916
98 Correct 10 ms 604 KB Correct answer: answer = 10680029
99 Correct 11 ms 716 KB Correct answer: answer = 18351700
100 Correct 9 ms 688 KB Correct answer: answer = 16040026
101 Correct 3 ms 460 KB Correct answer: answer = 253968628325
102 Correct 4 ms 424 KB Correct answer: answer = 10267
103 Correct 10 ms 736 KB Correct answer: answer = 2582408
104 Correct 2 ms 376 KB Correct answer: answer = 78024964781
105 Correct 2 ms 460 KB Correct answer: answer = 9866346457
106 Correct 3 ms 460 KB Correct answer: answer = 3327720949
107 Correct 3 ms 436 KB Correct answer: answer = 86064128360
108 Correct 3 ms 460 KB Correct answer: answer = 12698259150
109 Correct 9 ms 604 KB Correct answer: answer = 1185259288
110 Correct 19 ms 2464 KB Correct answer: answer = 999889968863
111 Correct 17 ms 2508 KB Correct answer: answer = 999861384931
112 Correct 16 ms 2508 KB Correct answer: answer = 999811809929
113 Correct 15 ms 2496 KB Correct answer: answer = 999869756441
114 Correct 91 ms 5344 KB Correct answer: answer = 1700000000
115 Correct 116 ms 5768 KB Correct answer: answer = 131666670
116 Correct 28 ms 1960 KB Correct answer: answer = 89478486
117 Correct 31 ms 2144 KB Correct answer: answer = 4971040
118 Correct 28 ms 2088 KB Correct answer: answer = 2711494
119 Correct 102 ms 5840 KB Correct answer: answer = 25252530
120 Correct 118 ms 5776 KB Correct answer: answer = 62500000
121 Correct 130 ms 4892 KB Correct answer: answer = 333175097780
122 Correct 143 ms 5088 KB Correct answer: answer = 33121180179
123 Correct 148 ms 4864 KB Correct answer: answer = 9802314015
124 Correct 146 ms 5916 KB Correct answer: answer = 32567551
125 Correct 117 ms 5932 KB Correct answer: answer = 997525000000
126 Correct 141 ms 4740 KB Correct answer: answer = 752723538884
127 Correct 12 ms 2448 KB Correct answer: answer = 1000000000000
128 Correct 14 ms 2476 KB Correct answer: answer = 999978000121
129 Correct 15 ms 2476 KB Correct answer: answer = 745986144735
130 Correct 10 ms 1988 KB Correct answer: answer = 2
131 Correct 136 ms 5784 KB Correct answer: answer = 277966670
132 Correct 116 ms 5356 KB Correct answer: answer = 2500900082
133 Correct 26 ms 2768 KB Correct answer: answer = 301248349636
134 Correct 64 ms 2736 KB Correct answer: answer = 14118891
135 Correct 20 ms 2460 KB Correct answer: answer = 14384977265
136 Correct 17 ms 2668 KB Correct answer: answer = 3681368330
137 Correct 17 ms 2472 KB Correct answer: answer = 2720316816

Subtask #6
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Correct answer: answer = 4
2 Correct 0 ms 204 KB Correct answer: answer = 4
3 Correct 1 ms 204 KB Correct answer: answer = 4
4 Correct 1 ms 204 KB Correct answer: answer = 12
5 Correct 0 ms 204 KB Correct answer: answer = 52
6 Correct 0 ms 204 KB Correct answer: answer = 210
7 Correct 0 ms 204 KB Correct answer: answer = 88
8 Correct 1 ms 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 0 ms 204 KB Correct answer: answer = 9502
12 Correct 1 ms 204 KB Correct answer: answer = 49
13 Correct 0 ms 204 KB Correct answer: answer = 151
14 Correct 1 ms 204 KB Correct answer: answer = 7550
15 Correct 1 ms 204 KB Correct answer: answer = 7220
16 Correct 1 ms 204 KB Correct answer: answer = 7550
17 Correct 1 ms 204 KB Correct answer: answer = 10000
18 Correct 0 ms 204 KB Correct answer: answer = 10000
19 Correct 1 ms 204 KB Correct answer: answer = 624
20 Correct 1 ms 204 KB Correct answer: answer = 10000
21 Correct 0 ms 204 KB Correct answer: answer = 1
22 Correct 0 ms 204 KB Correct answer: answer = 4
23 Correct 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 204 KB Correct answer: answer = 71923
27 Correct 1 ms 204 KB Correct answer: answer = 77137
28 Correct 2 ms 332 KB Correct answer: answer = 764
29 Correct 1 ms 332 KB Correct answer: answer = 250000
30 Correct 1 ms 332 KB Correct answer: answer = 500
31 Correct 1 ms 204 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 1 ms 204 KB Correct answer: answer = 796
36 Correct 1 ms 332 KB Correct answer: answer = 7580
37 Correct 1 ms 332 KB Correct answer: answer = 1904
38 Correct 1 ms 204 KB Correct answer: answer = 996004
39 Correct 1 ms 204 KB Correct answer: answer = 38817
40 Correct 1 ms 332 KB Correct answer: answer = 4096
41 Correct 0 ms 204 KB Correct answer: answer = 1
42 Correct 1 ms 204 KB Correct answer: answer = 1
43 Correct 1 ms 332 KB Correct answer: answer = 2040
44 Correct 1 ms 204 KB Correct answer: answer = 2
45 Correct 0 ms 204 KB Correct answer: answer = 4
46 Correct 0 ms 204 KB Correct answer: answer = 9
47 Correct 0 ms 204 KB Correct answer: answer = 9
48 Correct 0 ms 204 KB Correct answer: answer = 21
49 Correct 0 ms 204 KB Correct answer: answer = 71
50 Correct 1 ms 204 KB Correct answer: answer = 77
51 Correct 1 ms 204 KB Correct answer: answer = 400
52 Correct 1 ms 204 KB Correct answer: answer = 996004
53 Correct 1 ms 204 KB Correct answer: answer = 997310
54 Correct 1 ms 204 KB Correct answer: answer = 990781
55 Correct 1 ms 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 204 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 1 ms 204 KB Correct answer: answer = 1000000
66 Correct 0 ms 204 KB Correct answer: answer = 250000
67 Correct 1 ms 204 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 332 KB Correct answer: answer = 1504
73 Correct 1 ms 204 KB Correct answer: answer = 37486
74 Correct 1 ms 320 KB Correct answer: answer = 4284
75 Correct 1 ms 204 KB Correct answer: answer = 158008
76 Correct 1 ms 204 KB Correct answer: answer = 51860
77 Correct 1 ms 204 KB Correct answer: answer = 12985
78 Correct 2 ms 332 KB Correct answer: answer = 997864126212
79 Correct 2 ms 408 KB Correct answer: answer = 998608411647
80 Correct 2 ms 460 KB Correct answer: answer = 995265560477
81 Correct 6 ms 588 KB Correct answer: answer = 10125000
82 Correct 8 ms 588 KB Correct answer: answer = 2291668
83 Correct 4 ms 460 KB Correct answer: answer = 42388
84 Correct 4 ms 460 KB Correct answer: answer = 10318
85 Correct 4 ms 436 KB Correct answer: answer = 3416
86 Correct 12 ms 688 KB Correct answer: answer = 331708193881
87 Correct 12 ms 688 KB Correct answer: answer = 2861193756
88 Correct 12 ms 724 KB Correct answer: answer = 114646930
89 Correct 7 ms 716 KB Correct answer: answer = 9280921
90 Correct 9 ms 732 KB Correct answer: answer = 999984053400
91 Correct 11 ms 588 KB Correct answer: answer = 750935949134
92 Correct 2 ms 368 KB Correct answer: answer = 1000000000000
93 Correct 2 ms 432 KB Correct answer: answer = 998762383161
94 Correct 11 ms 556 KB Correct answer: answer = 23017412908
95 Correct 2 ms 432 KB Correct answer: answer = 728143410622
96 Correct 2 ms 332 KB Correct answer: answer = 2
97 Correct 11 ms 712 KB Correct answer: answer = 1824916
98 Correct 10 ms 604 KB Correct answer: answer = 10680029
99 Correct 11 ms 716 KB Correct answer: answer = 18351700
100 Correct 9 ms 688 KB Correct answer: answer = 16040026
101 Correct 3 ms 460 KB Correct answer: answer = 253968628325
102 Correct 4 ms 424 KB Correct answer: answer = 10267
103 Correct 10 ms 736 KB Correct answer: answer = 2582408
104 Correct 2 ms 376 KB Correct answer: answer = 78024964781
105 Correct 2 ms 460 KB Correct answer: answer = 9866346457
106 Correct 3 ms 460 KB Correct answer: answer = 3327720949
107 Correct 3 ms 436 KB Correct answer: answer = 86064128360
108 Correct 3 ms 460 KB Correct answer: answer = 12698259150
109 Correct 9 ms 604 KB Correct answer: answer = 1185259288
110 Correct 19 ms 2464 KB Correct answer: answer = 999889968863
111 Correct 17 ms 2508 KB Correct answer: answer = 999861384931
112 Correct 16 ms 2508 KB Correct answer: answer = 999811809929
113 Correct 15 ms 2496 KB Correct answer: answer = 999869756441
114 Correct 91 ms 5344 KB Correct answer: answer = 1700000000
115 Correct 116 ms 5768 KB Correct answer: answer = 131666670
116 Correct 28 ms 1960 KB Correct answer: answer = 89478486
117 Correct 31 ms 2144 KB Correct answer: answer = 4971040
118 Correct 28 ms 2088 KB Correct answer: answer = 2711494
119 Correct 102 ms 5840 KB Correct answer: answer = 25252530
120 Correct 118 ms 5776 KB Correct answer: answer = 62500000
121 Correct 130 ms 4892 KB Correct answer: answer = 333175097780
122 Correct 143 ms 5088 KB Correct answer: answer = 33121180179
123 Correct 148 ms 4864 KB Correct answer: answer = 9802314015
124 Correct 146 ms 5916 KB Correct answer: answer = 32567551
125 Correct 117 ms 5932 KB Correct answer: answer = 997525000000
126 Correct 141 ms 4740 KB Correct answer: answer = 752723538884
127 Correct 12 ms 2448 KB Correct answer: answer = 1000000000000
128 Correct 14 ms 2476 KB Correct answer: answer = 999978000121
129 Correct 15 ms 2476 KB Correct answer: answer = 745986144735
130 Correct 10 ms 1988 KB Correct answer: answer = 2
131 Correct 136 ms 5784 KB Correct answer: answer = 277966670
132 Correct 116 ms 5356 KB Correct answer: answer = 2500900082
133 Correct 26 ms 2768 KB Correct answer: answer = 301248349636
134 Correct 64 ms 2736 KB Correct answer: answer = 14118891
135 Correct 20 ms 2460 KB Correct answer: answer = 14384977265
136 Correct 17 ms 2668 KB Correct answer: answer = 3681368330
137 Correct 17 ms 2472 KB Correct answer: answer = 2720316816
138 Correct 29 ms 4676 KB Correct answer: answer = 999976000144
139 Correct 30 ms 4648 KB Correct answer: answer = 999856102410
140 Correct 34 ms 4652 KB Correct answer: answer = 999958401531
141 Correct 32 ms 4756 KB Correct answer: answer = 999769649944
142 Correct 33 ms 4764 KB Correct answer: answer = 999874525918
143 Correct 193 ms 10332 KB Correct answer: answer = 6050000000
144 Correct 212 ms 10928 KB Correct answer: answer = 1112500000
145 Correct 160 ms 7008 KB Correct answer: answer = 4294967296
146 Correct 138 ms 7588 KB Correct answer: answer = 87652406
147 Correct 133 ms 7740 KB Correct answer: answer = 6297664
148 Correct 154 ms 7756 KB Correct answer: answer = 196612
149 Correct 214 ms 11684 KB Correct answer: answer = 15015100
150 Correct 218 ms 11684 KB Correct answer: answer = 25000000
151 Correct 256 ms 9288 KB Correct answer: answer = 333230209550
152 Correct 296 ms 9320 KB Correct answer: answer = 917123769
153 Correct 297 ms 11548 KB Correct answer: answer = 95162
154 Correct 283 ms 11456 KB Correct answer: answer = 382616191
155 Correct 236 ms 11792 KB Correct answer: answer = 990033333400
156 Correct 258 ms 11928 KB Correct answer: answer = 990000100000
157 Correct 226 ms 10092 KB Correct answer: answer = 749998188180
158 Correct 22 ms 4644 KB Correct answer: answer = 1000000000000
159 Correct 34 ms 4764 KB Correct answer: answer = 999988000036
160 Correct 41 ms 4776 KB Correct answer: answer = 744929274393
161 Correct 22 ms 3756 KB Correct answer: answer = 2
162 Correct 235 ms 11652 KB Correct answer: answer = 1300024
163 Correct 263 ms 10572 KB Correct answer: answer = 5000700010
164 Correct 53 ms 5280 KB Correct answer: answer = 354997100800
165 Correct 125 ms 5780 KB Correct answer: answer = 257000
166 Correct 145 ms 6116 KB Correct answer: answer = 3765323
167 Correct 135 ms 6024 KB Correct answer: answer = 1525903
168 Correct 39 ms 4788 KB Correct answer: answer = 67618137730
169 Correct 29 ms 4780 KB Correct answer: answer = 12656680171
170 Correct 37 ms 4932 KB Correct answer: answer = 579831736
171 Correct 101 ms 6464 KB Correct answer: answer = 23605611
172 Correct 54 ms 5052 KB Correct answer: answer = 7052481200
173 Correct 59 ms 5520 KB Correct answer: answer = 1314039500
174 Correct 71 ms 6092 KB Correct answer: answer = 302484000
175 Correct 203 ms 8084 KB Correct answer: answer = 52348480