oj.uz

Submission #555785

# Submission time Handle Problem Language Result Execution time Memory
555785 2022-05-01T14:26:07 Z nots0fast Aliens (IOI16_aliens) C++17
100 / 100
 1245 ms 55600 KB 
#include "aliens.h"
#include <fstream>
#include <iostream>
#include <math.h>
#include <algorithm>
#include <assert.h>
using namespace std;
#define mp(a,b) make_pair(a,b)
#define ff first
#define setp setprecision(12)<<fixed
#define ss second
#define fori(v) for(ll i=0; i<v; i++)
#define forj(v) for(ll j=0; j<v; j++)
#define fork(v) for(ll k=0; k<v; k++)
#define forl(v) for(ll l=0; l<v; l++)
#define fort(v) for(ll t=0; t<v; t++)
#define forz(v) for(ll z=0; z<v; z++)
#define forx(v) for(ll x=0; x<v; x++)
#define ll long long
#define lll __int128
#define ld long double
#define pb(a) push_back(a)
// #define cout out
// #define cin in
ll inf = pow(10, 18);
ll modulo = pow(10,9) + 7;
double eps = 1e-10;
ifstream in;
ofstream out;


struct line{
    ll k, b;
    ll cnt;
    line(){}
    line(ll k1, ll b1, ll cn){
        k = k1, b = b1, cnt = cn;
    }    
};

ll func(line& cur, ll x){
    return cur.k * x + cur.b;
}

// min number of transitions
bool better(line& a, line& b, ll x){
    ll vl1 = func(a, x);
    ll vl2 = func(b, x);
    
    return (vl1 < vl2 || ( (vl1 == vl2) && (a.cnt < b.cnt) ));
}


#define MAX 2'100'010

line seg[MAX];
// ql = -inf, qr = inf

// O(q * log^2(n)) for range updates

void add(ll hd, ll l, ll r, ll ql, ll qr, line cur){
    if(qr < l || r < ql){
        return;
    }
    ll mid = (l+r)/2;
    if(ql <= l && r <= qr){
        // O(log(n))
        bool md = better(cur, seg[hd], mid);
        bool lf = better(cur, seg[hd], l) ;
        if(md){
                swap(seg[hd], cur);
        }
        if(l == r){
                return;
        }
        if(md == lf){
                add(2*hd + 1, mid+1, r, ql, qr, cur);
        }
        else{
                add(2*hd, l, mid, ql, qr, cur);
        }
    }
    else{
        add(2*hd + 1, mid+1, r, ql, qr, cur);
        add(2*hd, l, mid, ql, qr, cur);
    }
}

// [l ... r]

void que(ll hd, ll l, ll r , ll x, line& best){
    if(better(seg[hd], best, x)){
        best = seg[hd];
    }
    
    if(l == r){
        return;
    }
    
    ll mid = (l+r)/2;
    if(x <= mid){
        que(hd*2, l, mid, x, best);
    }
    else{
        que(hd*2+1, mid+1, r, x, best);
    }
}


bool J(pair<ll, ll>& a, pair<ll ,ll>& b){
      if(a.ff != b.ff){
            return a.ff < b.ff;
      }
      return a.ss > b.ss;
}

void calc(vector<pair<ll, ll> >& arr, vector<ll>& dp, vector<ll>& tot, ll& lamda, ll m){
    fori(MAX){
        seg[i] = line(0, inf, 0);
    }
    ll n = arr.size();
    dp = vector<ll>(n, inf);
    tot = vector<ll>(n, inf);
    dp[0] =0, tot[0] = 0;
    for(ll i = 1; i<n; i++){
        ll li = arr[i].ff, ri = arr[i].ss;
        ll rp = arr[i-1].ss;
        ll k, b;
        b = li * li + dp[i-1] - lamda;
        if(rp > li){
            b -= (rp - li) * (rp - li);
        }
        k = -2*li;
        add(1, 0, m, 0, m, line(k, b, tot[i-1] + 1));
        line best(0, inf, 0);
        que(1, 0, m, ri, best);
        
        dp[i] = func(best, ri) + ri*ri;
        tot[i] = best.cnt;
    }
}


long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
    m+=10;
    vector<pair<ll, ll> > arr;
    fori(n){
        if(r[i] > c[i]){
            swap(r[i], c[i]);
        }
        arr.pb(mp(r[i], c[i]));
    }
    
    sort(arr.begin(), arr.end(), J);
    {
        ll mxc = -inf;
        vector<pair<ll, ll> > good({mp(-inf, -inf)});
        fori(n){
                ll ri = arr[i].ff, ci = arr[i].ss;
                if(ci > mxc){
                    good.pb(mp(ri, ci));
                    mxc = ci;
                }
        }
        arr = good;
    }
    n = arr.size();
    
    for(auto& el : arr){
        ++el.ss;
    }
    
    ll lo = -2e12, hi = 0;
    
    while(lo < hi){
        ll mid = (lo + hi)/2;
        // has to be closer to high
        if(hi - mid > mid - lo){
            ++mid;
        }
        
        vector<ll> dp, tot;
        calc(arr, dp, tot, mid, m);
        if(tot[n-1] > k){
            hi = mid-1;
        }
        else{
            lo = mid;
        }
    }
    
    vector<ll> dp, tot;
    calc(arr, dp, tot, lo, m);
    
//   cout<<"lamda is "<<lo<<" dp came out "<<dp[n-1]<<endl;
    
    // it is definitely k / or maybe smaller than k ????
    
    if(k == n){
        assert(lo == 0);
    }
    
    return dp[n-1] + k * lo;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 49492 KB Correct answer: answer = 4
2 Correct 255 ms 49484 KB Correct answer: answer = 4
3 Correct 268 ms 49596 KB Correct answer: answer = 4
4 Correct 259 ms 49592 KB Correct answer: answer = 12
5 Correct 255 ms 49596 KB Correct answer: answer = 52
6 Correct 266 ms 49600 KB Correct answer: answer = 210
7 Correct 259 ms 49520 KB Correct answer: answer = 88
8 Correct 258 ms 49596 KB Correct answer: answer = 7696
9 Correct 259 ms 49600 KB Correct answer: answer = 1
10 Correct 254 ms 49704 KB Correct answer: answer = 2374
11 Correct 255 ms 49484 KB Correct answer: answer = 9502
12 Correct 256 ms 49596 KB Correct answer: answer = 49
13 Correct 268 ms 49620 KB Correct answer: answer = 151
14 Correct 256 ms 49612 KB Correct answer: answer = 7550
15 Correct 256 ms 49612 KB Correct answer: answer = 7220
16 Correct 258 ms 49604 KB Correct answer: answer = 7550
17 Correct 257 ms 49600 KB Correct answer: answer = 10000
18 Correct 270 ms 49596 KB Correct answer: answer = 10000
19 Correct 261 ms 49600 KB Correct answer: answer = 624
20 Correct 257 ms 49680 KB Correct answer: answer = 10000

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 49588 KB Correct answer: answer = 1
2 Correct 253 ms 49592 KB Correct answer: answer = 4
3 Correct 261 ms 49592 KB Correct answer: answer = 1
4 Correct 258 ms 49592 KB Correct answer: answer = 5
5 Correct 272 ms 49600 KB Correct answer: answer = 41
6 Correct 255 ms 49596 KB Correct answer: answer = 71923
7 Correct 274 ms 49624 KB Correct answer: answer = 77137
8 Correct 285 ms 49620 KB Correct answer: answer = 764
9 Correct 279 ms 49624 KB Correct answer: answer = 250000
10 Correct 264 ms 49632 KB Correct answer: answer = 500
11 Correct 258 ms 49492 KB Correct answer: answer = 32
12 Correct 259 ms 49624 KB Correct answer: answer = 130050
13 Correct 257 ms 49624 KB Correct answer: answer = 5110
14 Correct 253 ms 49620 KB Correct answer: answer = 2626
15 Correct 273 ms 49620 KB Correct answer: answer = 796
16 Correct 258 ms 49556 KB Correct answer: answer = 7580
17 Correct 262 ms 49624 KB Correct answer: answer = 1904
18 Correct 260 ms 49624 KB Correct answer: answer = 996004
19 Correct 276 ms 49620 KB Correct answer: answer = 38817
20 Correct 262 ms 49628 KB Correct answer: answer = 4096
21 Correct 259 ms 49616 KB Correct answer: answer = 1
22 Correct 256 ms 49620 KB Correct answer: answer = 1
23 Correct 265 ms 49624 KB Correct answer: answer = 2040
24 Correct 259 ms 49628 KB Correct answer: answer = 2

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 49492 KB Correct answer: answer = 4
2 Correct 255 ms 49484 KB Correct answer: answer = 4
3 Correct 268 ms 49596 KB Correct answer: answer = 4
4 Correct 259 ms 49592 KB Correct answer: answer = 12
5 Correct 255 ms 49596 KB Correct answer: answer = 52
6 Correct 266 ms 49600 KB Correct answer: answer = 210
7 Correct 259 ms 49520 KB Correct answer: answer = 88
8 Correct 258 ms 49596 KB Correct answer: answer = 7696
9 Correct 259 ms 49600 KB Correct answer: answer = 1
10 Correct 254 ms 49704 KB Correct answer: answer = 2374
11 Correct 255 ms 49484 KB Correct answer: answer = 9502
12 Correct 256 ms 49596 KB Correct answer: answer = 49
13 Correct 268 ms 49620 KB Correct answer: answer = 151
14 Correct 256 ms 49612 KB Correct answer: answer = 7550
15 Correct 256 ms 49612 KB Correct answer: answer = 7220
16 Correct 258 ms 49604 KB Correct answer: answer = 7550
17 Correct 257 ms 49600 KB Correct answer: answer = 10000
18 Correct 270 ms 49596 KB Correct answer: answer = 10000
19 Correct 261 ms 49600 KB Correct answer: answer = 624
20 Correct 257 ms 49680 KB Correct answer: answer = 10000
21 Correct 266 ms 49588 KB Correct answer: answer = 1
22 Correct 253 ms 49592 KB Correct answer: answer = 4
23 Correct 261 ms 49592 KB Correct answer: answer = 1
24 Correct 258 ms 49592 KB Correct answer: answer = 5
25 Correct 272 ms 49600 KB Correct answer: answer = 41
26 Correct 255 ms 49596 KB Correct answer: answer = 71923
27 Correct 274 ms 49624 KB Correct answer: answer = 77137
28 Correct 285 ms 49620 KB Correct answer: answer = 764
29 Correct 279 ms 49624 KB Correct answer: answer = 250000
30 Correct 264 ms 49632 KB Correct answer: answer = 500
31 Correct 258 ms 49492 KB Correct answer: answer = 32
32 Correct 259 ms 49624 KB Correct answer: answer = 130050
33 Correct 257 ms 49624 KB Correct answer: answer = 5110
34 Correct 253 ms 49620 KB Correct answer: answer = 2626
35 Correct 273 ms 49620 KB Correct answer: answer = 796
36 Correct 258 ms 49556 KB Correct answer: answer = 7580
37 Correct 262 ms 49624 KB Correct answer: answer = 1904
38 Correct 260 ms 49624 KB Correct answer: answer = 996004
39 Correct 276 ms 49620 KB Correct answer: answer = 38817
40 Correct 262 ms 49628 KB Correct answer: answer = 4096
41 Correct 259 ms 49616 KB Correct answer: answer = 1
42 Correct 256 ms 49620 KB Correct answer: answer = 1
43 Correct 265 ms 49624 KB Correct answer: answer = 2040
44 Correct 259 ms 49628 KB Correct answer: answer = 2
45 Correct 255 ms 49612 KB Correct answer: answer = 4
46 Correct 260 ms 49608 KB Correct answer: answer = 9
47 Correct 262 ms 49484 KB Correct answer: answer = 9
48 Correct 257 ms 49668 KB Correct answer: answer = 21
49 Correct 265 ms 49592 KB Correct answer: answer = 71
50 Correct 260 ms 49596 KB Correct answer: answer = 77
51 Correct 262 ms 49596 KB Correct answer: answer = 400
52 Correct 264 ms 49620 KB Correct answer: answer = 996004
53 Correct 266 ms 49616 KB Correct answer: answer = 997310
54 Correct 260 ms 49620 KB Correct answer: answer = 990781
55 Correct 264 ms 49616 KB Correct answer: answer = 996545
56 Correct 257 ms 49584 KB Correct answer: answer = 484
57 Correct 264 ms 49500 KB Correct answer: answer = 484
58 Correct 260 ms 49624 KB Correct answer: answer = 63501
59 Correct 260 ms 49624 KB Correct answer: answer = 323501
60 Correct 259 ms 49716 KB Correct answer: answer = 752500
61 Correct 257 ms 49624 KB Correct answer: answer = 761480
62 Correct 255 ms 49620 KB Correct answer: answer = 758932
63 Correct 267 ms 49612 KB Correct answer: answer = 1000000
64 Correct 261 ms 49692 KB Correct answer: answer = 750500
65 Correct 260 ms 49624 KB Correct answer: answer = 1000000
66 Correct 259 ms 49732 KB Correct answer: answer = 250000
67 Correct 274 ms 49616 KB Correct answer: answer = 250000
68 Correct 263 ms 49620 KB Correct answer: answer = 1000000
69 Correct 261 ms 49616 KB Correct answer: answer = 994009
70 Correct 257 ms 49616 KB Correct answer: answer = 59315
71 Correct 257 ms 49620 KB Correct answer: answer = 25454
72 Correct 273 ms 49624 KB Correct answer: answer = 1504
73 Correct 256 ms 49620 KB Correct answer: answer = 37486
74 Correct 257 ms 49620 KB Correct answer: answer = 4284
75 Correct 262 ms 49792 KB Correct answer: answer = 158008
76 Correct 258 ms 49616 KB Correct answer: answer = 51860
77 Correct 258 ms 49620 KB Correct answer: answer = 12985

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 49492 KB Correct answer: answer = 4
2 Correct 255 ms 49484 KB Correct answer: answer = 4
3 Correct 268 ms 49596 KB Correct answer: answer = 4
4 Correct 259 ms 49592 KB Correct answer: answer = 12
5 Correct 255 ms 49596 KB Correct answer: answer = 52
6 Correct 266 ms 49600 KB Correct answer: answer = 210
7 Correct 259 ms 49520 KB Correct answer: answer = 88
8 Correct 258 ms 49596 KB Correct answer: answer = 7696
9 Correct 259 ms 49600 KB Correct answer: answer = 1
10 Correct 254 ms 49704 KB Correct answer: answer = 2374
11 Correct 255 ms 49484 KB Correct answer: answer = 9502
12 Correct 256 ms 49596 KB Correct answer: answer = 49
13 Correct 268 ms 49620 KB Correct answer: answer = 151
14 Correct 256 ms 49612 KB Correct answer: answer = 7550
15 Correct 256 ms 49612 KB Correct answer: answer = 7220
16 Correct 258 ms 49604 KB Correct answer: answer = 7550
17 Correct 257 ms 49600 KB Correct answer: answer = 10000
18 Correct 270 ms 49596 KB Correct answer: answer = 10000
19 Correct 261 ms 49600 KB Correct answer: answer = 624
20 Correct 257 ms 49680 KB Correct answer: answer = 10000
21 Correct 266 ms 49588 KB Correct answer: answer = 1
22 Correct 253 ms 49592 KB Correct answer: answer = 4
23 Correct 261 ms 49592 KB Correct answer: answer = 1
24 Correct 258 ms 49592 KB Correct answer: answer = 5
25 Correct 272 ms 49600 KB Correct answer: answer = 41
26 Correct 255 ms 49596 KB Correct answer: answer = 71923
27 Correct 274 ms 49624 KB Correct answer: answer = 77137
28 Correct 285 ms 49620 KB Correct answer: answer = 764
29 Correct 279 ms 49624 KB Correct answer: answer = 250000
30 Correct 264 ms 49632 KB Correct answer: answer = 500
31 Correct 258 ms 49492 KB Correct answer: answer = 32
32 Correct 259 ms 49624 KB Correct answer: answer = 130050
33 Correct 257 ms 49624 KB Correct answer: answer = 5110
34 Correct 253 ms 49620 KB Correct answer: answer = 2626
35 Correct 273 ms 49620 KB Correct answer: answer = 796
36 Correct 258 ms 49556 KB Correct answer: answer = 7580
37 Correct 262 ms 49624 KB Correct answer: answer = 1904
38 Correct 260 ms 49624 KB Correct answer: answer = 996004
39 Correct 276 ms 49620 KB Correct answer: answer = 38817
40 Correct 262 ms 49628 KB Correct answer: answer = 4096
41 Correct 259 ms 49616 KB Correct answer: answer = 1
42 Correct 256 ms 49620 KB Correct answer: answer = 1
43 Correct 265 ms 49624 KB Correct answer: answer = 2040
44 Correct 259 ms 49628 KB Correct answer: answer = 2
45 Correct 255 ms 49612 KB Correct answer: answer = 4
46 Correct 260 ms 49608 KB Correct answer: answer = 9
47 Correct 262 ms 49484 KB Correct answer: answer = 9
48 Correct 257 ms 49668 KB Correct answer: answer = 21
49 Correct 265 ms 49592 KB Correct answer: answer = 71
50 Correct 260 ms 49596 KB Correct answer: answer = 77
51 Correct 262 ms 49596 KB Correct answer: answer = 400
52 Correct 264 ms 49620 KB Correct answer: answer = 996004
53 Correct 266 ms 49616 KB Correct answer: answer = 997310
54 Correct 260 ms 49620 KB Correct answer: answer = 990781
55 Correct 264 ms 49616 KB Correct answer: answer = 996545
56 Correct 257 ms 49584 KB Correct answer: answer = 484
57 Correct 264 ms 49500 KB Correct answer: answer = 484
58 Correct 260 ms 49624 KB Correct answer: answer = 63501
59 Correct 260 ms 49624 KB Correct answer: answer = 323501
60 Correct 259 ms 49716 KB Correct answer: answer = 752500
61 Correct 257 ms 49624 KB Correct answer: answer = 761480
62 Correct 255 ms 49620 KB Correct answer: answer = 758932
63 Correct 267 ms 49612 KB Correct answer: answer = 1000000
64 Correct 261 ms 49692 KB Correct answer: answer = 750500
65 Correct 260 ms 49624 KB Correct answer: answer = 1000000
66 Correct 259 ms 49732 KB Correct answer: answer = 250000
67 Correct 274 ms 49616 KB Correct answer: answer = 250000
68 Correct 263 ms 49620 KB Correct answer: answer = 1000000
69 Correct 261 ms 49616 KB Correct answer: answer = 994009
70 Correct 257 ms 49616 KB Correct answer: answer = 59315
71 Correct 257 ms 49620 KB Correct answer: answer = 25454
72 Correct 273 ms 49624 KB Correct answer: answer = 1504
73 Correct 256 ms 49620 KB Correct answer: answer = 37486
74 Correct 257 ms 49620 KB Correct answer: answer = 4284
75 Correct 262 ms 49792 KB Correct answer: answer = 158008
76 Correct 258 ms 49616 KB Correct answer: answer = 51860
77 Correct 258 ms 49620 KB Correct answer: answer = 12985
78 Correct 258 ms 49884 KB Correct answer: answer = 997864126212
79 Correct 263 ms 49840 KB Correct answer: answer = 998608411647
80 Correct 258 ms 49844 KB Correct answer: answer = 995265560477
81 Correct 279 ms 49888 KB Correct answer: answer = 10125000
82 Correct 292 ms 49944 KB Correct answer: answer = 2291668
83 Correct 286 ms 49732 KB Correct answer: answer = 42388
84 Correct 269 ms 49816 KB Correct answer: answer = 10318
85 Correct 284 ms 49812 KB Correct answer: answer = 3416
86 Correct 308 ms 49976 KB Correct answer: answer = 331708193881
87 Correct 330 ms 49908 KB Correct answer: answer = 2861193756
88 Correct 321 ms 49908 KB Correct answer: answer = 114646930
89 Correct 287 ms 49896 KB Correct answer: answer = 9280921
90 Correct 292 ms 49896 KB Correct answer: answer = 999984053400
91 Correct 321 ms 49904 KB Correct answer: answer = 750935949134
92 Correct 259 ms 49840 KB Correct answer: answer = 1000000000000
93 Correct 265 ms 49740 KB Correct answer: answer = 998762383161
94 Correct 313 ms 49908 KB Correct answer: answer = 23017412908
95 Correct 271 ms 49848 KB Correct answer: answer = 728143410622
96 Correct 259 ms 49804 KB Correct answer: answer = 2
97 Correct 305 ms 49888 KB Correct answer: answer = 1824916
98 Correct 306 ms 49896 KB Correct answer: answer = 10680029
99 Correct 300 ms 49900 KB Correct answer: answer = 18351700
100 Correct 289 ms 49984 KB Correct answer: answer = 16040026
101 Correct 270 ms 49840 KB Correct answer: answer = 253968628325
102 Correct 278 ms 49744 KB Correct answer: answer = 10267
103 Correct 307 ms 49980 KB Correct answer: answer = 2582408
104 Correct 258 ms 49840 KB Correct answer: answer = 78024964781
105 Correct 267 ms 49844 KB Correct answer: answer = 9866346457
106 Correct 276 ms 49840 KB Correct answer: answer = 3327720949
107 Correct 262 ms 49868 KB Correct answer: answer = 86064128360
108 Correct 279 ms 49848 KB Correct answer: answer = 12698259150
109 Correct 308 ms 49888 KB Correct answer: answer = 1185259288

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 49492 KB Correct answer: answer = 4
2 Correct 255 ms 49484 KB Correct answer: answer = 4
3 Correct 268 ms 49596 KB Correct answer: answer = 4
4 Correct 259 ms 49592 KB Correct answer: answer = 12
5 Correct 255 ms 49596 KB Correct answer: answer = 52
6 Correct 266 ms 49600 KB Correct answer: answer = 210
7 Correct 259 ms 49520 KB Correct answer: answer = 88
8 Correct 258 ms 49596 KB Correct answer: answer = 7696
9 Correct 259 ms 49600 KB Correct answer: answer = 1
10 Correct 254 ms 49704 KB Correct answer: answer = 2374
11 Correct 255 ms 49484 KB Correct answer: answer = 9502
12 Correct 256 ms 49596 KB Correct answer: answer = 49
13 Correct 268 ms 49620 KB Correct answer: answer = 151
14 Correct 256 ms 49612 KB Correct answer: answer = 7550
15 Correct 256 ms 49612 KB Correct answer: answer = 7220
16 Correct 258 ms 49604 KB Correct answer: answer = 7550
17 Correct 257 ms 49600 KB Correct answer: answer = 10000
18 Correct 270 ms 49596 KB Correct answer: answer = 10000
19 Correct 261 ms 49600 KB Correct answer: answer = 624
20 Correct 257 ms 49680 KB Correct answer: answer = 10000
21 Correct 266 ms 49588 KB Correct answer: answer = 1
22 Correct 253 ms 49592 KB Correct answer: answer = 4
23 Correct 261 ms 49592 KB Correct answer: answer = 1
24 Correct 258 ms 49592 KB Correct answer: answer = 5
25 Correct 272 ms 49600 KB Correct answer: answer = 41
26 Correct 255 ms 49596 KB Correct answer: answer = 71923
27 Correct 274 ms 49624 KB Correct answer: answer = 77137
28 Correct 285 ms 49620 KB Correct answer: answer = 764
29 Correct 279 ms 49624 KB Correct answer: answer = 250000
30 Correct 264 ms 49632 KB Correct answer: answer = 500
31 Correct 258 ms 49492 KB Correct answer: answer = 32
32 Correct 259 ms 49624 KB Correct answer: answer = 130050
33 Correct 257 ms 49624 KB Correct answer: answer = 5110
34 Correct 253 ms 49620 KB Correct answer: answer = 2626
35 Correct 273 ms 49620 KB Correct answer: answer = 796
36 Correct 258 ms 49556 KB Correct answer: answer = 7580
37 Correct 262 ms 49624 KB Correct answer: answer = 1904
38 Correct 260 ms 49624 KB Correct answer: answer = 996004
39 Correct 276 ms 49620 KB Correct answer: answer = 38817
40 Correct 262 ms 49628 KB Correct answer: answer = 4096
41 Correct 259 ms 49616 KB Correct answer: answer = 1
42 Correct 256 ms 49620 KB Correct answer: answer = 1
43 Correct 265 ms 49624 KB Correct answer: answer = 2040
44 Correct 259 ms 49628 KB Correct answer: answer = 2
45 Correct 255 ms 49612 KB Correct answer: answer = 4
46 Correct 260 ms 49608 KB Correct answer: answer = 9
47 Correct 262 ms 49484 KB Correct answer: answer = 9
48 Correct 257 ms 49668 KB Correct answer: answer = 21
49 Correct 265 ms 49592 KB Correct answer: answer = 71
50 Correct 260 ms 49596 KB Correct answer: answer = 77
51 Correct 262 ms 49596 KB Correct answer: answer = 400
52 Correct 264 ms 49620 KB Correct answer: answer = 996004
53 Correct 266 ms 49616 KB Correct answer: answer = 997310
54 Correct 260 ms 49620 KB Correct answer: answer = 990781
55 Correct 264 ms 49616 KB Correct answer: answer = 996545
56 Correct 257 ms 49584 KB Correct answer: answer = 484
57 Correct 264 ms 49500 KB Correct answer: answer = 484
58 Correct 260 ms 49624 KB Correct answer: answer = 63501
59 Correct 260 ms 49624 KB Correct answer: answer = 323501
60 Correct 259 ms 49716 KB Correct answer: answer = 752500
61 Correct 257 ms 49624 KB Correct answer: answer = 761480
62 Correct 255 ms 49620 KB Correct answer: answer = 758932
63 Correct 267 ms 49612 KB Correct answer: answer = 1000000
64 Correct 261 ms 49692 KB Correct answer: answer = 750500
65 Correct 260 ms 49624 KB Correct answer: answer = 1000000
66 Correct 259 ms 49732 KB Correct answer: answer = 250000
67 Correct 274 ms 49616 KB Correct answer: answer = 250000
68 Correct 263 ms 49620 KB Correct answer: answer = 1000000
69 Correct 261 ms 49616 KB Correct answer: answer = 994009
70 Correct 257 ms 49616 KB Correct answer: answer = 59315
71 Correct 257 ms 49620 KB Correct answer: answer = 25454
72 Correct 273 ms 49624 KB Correct answer: answer = 1504
73 Correct 256 ms 49620 KB Correct answer: answer = 37486
74 Correct 257 ms 49620 KB Correct answer: answer = 4284
75 Correct 262 ms 49792 KB Correct answer: answer = 158008
76 Correct 258 ms 49616 KB Correct answer: answer = 51860
77 Correct 258 ms 49620 KB Correct answer: answer = 12985
78 Correct 258 ms 49884 KB Correct answer: answer = 997864126212
79 Correct 263 ms 49840 KB Correct answer: answer = 998608411647
80 Correct 258 ms 49844 KB Correct answer: answer = 995265560477
81 Correct 279 ms 49888 KB Correct answer: answer = 10125000
82 Correct 292 ms 49944 KB Correct answer: answer = 2291668
83 Correct 286 ms 49732 KB Correct answer: answer = 42388
84 Correct 269 ms 49816 KB Correct answer: answer = 10318
85 Correct 284 ms 49812 KB Correct answer: answer = 3416
86 Correct 308 ms 49976 KB Correct answer: answer = 331708193881
87 Correct 330 ms 49908 KB Correct answer: answer = 2861193756
88 Correct 321 ms 49908 KB Correct answer: answer = 114646930
89 Correct 287 ms 49896 KB Correct answer: answer = 9280921
90 Correct 292 ms 49896 KB Correct answer: answer = 999984053400
91 Correct 321 ms 49904 KB Correct answer: answer = 750935949134
92 Correct 259 ms 49840 KB Correct answer: answer = 1000000000000
93 Correct 265 ms 49740 KB Correct answer: answer = 998762383161
94 Correct 313 ms 49908 KB Correct answer: answer = 23017412908
95 Correct 271 ms 49848 KB Correct answer: answer = 728143410622
96 Correct 259 ms 49804 KB Correct answer: answer = 2
97 Correct 305 ms 49888 KB Correct answer: answer = 1824916
98 Correct 306 ms 49896 KB Correct answer: answer = 10680029
99 Correct 300 ms 49900 KB Correct answer: answer = 18351700
100 Correct 289 ms 49984 KB Correct answer: answer = 16040026
101 Correct 270 ms 49840 KB Correct answer: answer = 253968628325
102 Correct 278 ms 49744 KB Correct answer: answer = 10267
103 Correct 307 ms 49980 KB Correct answer: answer = 2582408
104 Correct 258 ms 49840 KB Correct answer: answer = 78024964781
105 Correct 267 ms 49844 KB Correct answer: answer = 9866346457
106 Correct 276 ms 49840 KB Correct answer: answer = 3327720949
107 Correct 262 ms 49868 KB Correct answer: answer = 86064128360
108 Correct 279 ms 49848 KB Correct answer: answer = 12698259150
109 Correct 308 ms 49888 KB Correct answer: answer = 1185259288
110 Correct 272 ms 51872 KB Correct answer: answer = 999889968863
111 Correct 275 ms 51868 KB Correct answer: answer = 999861384931
112 Correct 273 ms 51888 KB Correct answer: answer = 999811809929
113 Correct 301 ms 51876 KB Correct answer: answer = 999869756441
114 Correct 588 ms 52408 KB Correct answer: answer = 1700000000
115 Correct 646 ms 52444 KB Correct answer: answer = 131666670
116 Correct 364 ms 50536 KB Correct answer: answer = 89478486
117 Correct 373 ms 50560 KB Correct answer: answer = 4971040
118 Correct 367 ms 50540 KB Correct answer: answer = 2711494
119 Correct 634 ms 52444 KB Correct answer: answer = 25252530
120 Correct 636 ms 52512 KB Correct answer: answer = 62500000
121 Correct 808 ms 52556 KB Correct answer: answer = 333175097780
122 Correct 833 ms 52552 KB Correct answer: answer = 33121180179
123 Correct 821 ms 52552 KB Correct answer: answer = 9802314015
124 Correct 622 ms 52440 KB Correct answer: answer = 32567551
125 Correct 716 ms 52496 KB Correct answer: answer = 997525000000
126 Correct 726 ms 52476 KB Correct answer: answer = 752723538884
127 Correct 268 ms 51836 KB Correct answer: answer = 1000000000000
128 Correct 272 ms 51904 KB Correct answer: answer = 999978000121
129 Correct 277 ms 51860 KB Correct answer: answer = 745986144735
130 Correct 278 ms 51492 KB Correct answer: answer = 2
131 Correct 713 ms 52484 KB Correct answer: answer = 277966670
132 Correct 656 ms 52532 KB Correct answer: answer = 2500900082
133 Correct 326 ms 51904 KB Correct answer: answer = 301248349636
134 Correct 461 ms 50988 KB Correct answer: answer = 14118891
135 Correct 277 ms 51880 KB Correct answer: answer = 14384977265
136 Correct 293 ms 51928 KB Correct answer: answer = 3681368330
137 Correct 294 ms 51904 KB Correct answer: answer = 2720316816

Subtask #6
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 49492 KB Correct answer: answer = 4
2 Correct 255 ms 49484 KB Correct answer: answer = 4
3 Correct 268 ms 49596 KB Correct answer: answer = 4
4 Correct 259 ms 49592 KB Correct answer: answer = 12
5 Correct 255 ms 49596 KB Correct answer: answer = 52
6 Correct 266 ms 49600 KB Correct answer: answer = 210
7 Correct 259 ms 49520 KB Correct answer: answer = 88
8 Correct 258 ms 49596 KB Correct answer: answer = 7696
9 Correct 259 ms 49600 KB Correct answer: answer = 1
10 Correct 254 ms 49704 KB Correct answer: answer = 2374
11 Correct 255 ms 49484 KB Correct answer: answer = 9502
12 Correct 256 ms 49596 KB Correct answer: answer = 49
13 Correct 268 ms 49620 KB Correct answer: answer = 151
14 Correct 256 ms 49612 KB Correct answer: answer = 7550
15 Correct 256 ms 49612 KB Correct answer: answer = 7220
16 Correct 258 ms 49604 KB Correct answer: answer = 7550
17 Correct 257 ms 49600 KB Correct answer: answer = 10000
18 Correct 270 ms 49596 KB Correct answer: answer = 10000
19 Correct 261 ms 49600 KB Correct answer: answer = 624
20 Correct 257 ms 49680 KB Correct answer: answer = 10000
21 Correct 266 ms 49588 KB Correct answer: answer = 1
22 Correct 253 ms 49592 KB Correct answer: answer = 4
23 Correct 261 ms 49592 KB Correct answer: answer = 1
24 Correct 258 ms 49592 KB Correct answer: answer = 5
25 Correct 272 ms 49600 KB Correct answer: answer = 41
26 Correct 255 ms 49596 KB Correct answer: answer = 71923
27 Correct 274 ms 49624 KB Correct answer: answer = 77137
28 Correct 285 ms 49620 KB Correct answer: answer = 764
29 Correct 279 ms 49624 KB Correct answer: answer = 250000
30 Correct 264 ms 49632 KB Correct answer: answer = 500
31 Correct 258 ms 49492 KB Correct answer: answer = 32
32 Correct 259 ms 49624 KB Correct answer: answer = 130050
33 Correct 257 ms 49624 KB Correct answer: answer = 5110
34 Correct 253 ms 49620 KB Correct answer: answer = 2626
35 Correct 273 ms 49620 KB Correct answer: answer = 796
36 Correct 258 ms 49556 KB Correct answer: answer = 7580
37 Correct 262 ms 49624 KB Correct answer: answer = 1904
38 Correct 260 ms 49624 KB Correct answer: answer = 996004
39 Correct 276 ms 49620 KB Correct answer: answer = 38817
40 Correct 262 ms 49628 KB Correct answer: answer = 4096
41 Correct 259 ms 49616 KB Correct answer: answer = 1
42 Correct 256 ms 49620 KB Correct answer: answer = 1
43 Correct 265 ms 49624 KB Correct answer: answer = 2040
44 Correct 259 ms 49628 KB Correct answer: answer = 2
45 Correct 255 ms 49612 KB Correct answer: answer = 4
46 Correct 260 ms 49608 KB Correct answer: answer = 9
47 Correct 262 ms 49484 KB Correct answer: answer = 9
48 Correct 257 ms 49668 KB Correct answer: answer = 21
49 Correct 265 ms 49592 KB Correct answer: answer = 71
50 Correct 260 ms 49596 KB Correct answer: answer = 77
51 Correct 262 ms 49596 KB Correct answer: answer = 400
52 Correct 264 ms 49620 KB Correct answer: answer = 996004
53 Correct 266 ms 49616 KB Correct answer: answer = 997310
54 Correct 260 ms 49620 KB Correct answer: answer = 990781
55 Correct 264 ms 49616 KB Correct answer: answer = 996545
56 Correct 257 ms 49584 KB Correct answer: answer = 484
57 Correct 264 ms 49500 KB Correct answer: answer = 484
58 Correct 260 ms 49624 KB Correct answer: answer = 63501
59 Correct 260 ms 49624 KB Correct answer: answer = 323501
60 Correct 259 ms 49716 KB Correct answer: answer = 752500
61 Correct 257 ms 49624 KB Correct answer: answer = 761480
62 Correct 255 ms 49620 KB Correct answer: answer = 758932
63 Correct 267 ms 49612 KB Correct answer: answer = 1000000
64 Correct 261 ms 49692 KB Correct answer: answer = 750500
65 Correct 260 ms 49624 KB Correct answer: answer = 1000000
66 Correct 259 ms 49732 KB Correct answer: answer = 250000
67 Correct 274 ms 49616 KB Correct answer: answer = 250000
68 Correct 263 ms 49620 KB Correct answer: answer = 1000000
69 Correct 261 ms 49616 KB Correct answer: answer = 994009
70 Correct 257 ms 49616 KB Correct answer: answer = 59315
71 Correct 257 ms 49620 KB Correct answer: answer = 25454
72 Correct 273 ms 49624 KB Correct answer: answer = 1504
73 Correct 256 ms 49620 KB Correct answer: answer = 37486
74 Correct 257 ms 49620 KB Correct answer: answer = 4284
75 Correct 262 ms 49792 KB Correct answer: answer = 158008
76 Correct 258 ms 49616 KB Correct answer: answer = 51860
77 Correct 258 ms 49620 KB Correct answer: answer = 12985
78 Correct 258 ms 49884 KB Correct answer: answer = 997864126212
79 Correct 263 ms 49840 KB Correct answer: answer = 998608411647
80 Correct 258 ms 49844 KB Correct answer: answer = 995265560477
81 Correct 279 ms 49888 KB Correct answer: answer = 10125000
82 Correct 292 ms 49944 KB Correct answer: answer = 2291668
83 Correct 286 ms 49732 KB Correct answer: answer = 42388
84 Correct 269 ms 49816 KB Correct answer: answer = 10318
85 Correct 284 ms 49812 KB Correct answer: answer = 3416
86 Correct 308 ms 49976 KB Correct answer: answer = 331708193881
87 Correct 330 ms 49908 KB Correct answer: answer = 2861193756
88 Correct 321 ms 49908 KB Correct answer: answer = 114646930
89 Correct 287 ms 49896 KB Correct answer: answer = 9280921
90 Correct 292 ms 49896 KB Correct answer: answer = 999984053400
91 Correct 321 ms 49904 KB Correct answer: answer = 750935949134
92 Correct 259 ms 49840 KB Correct answer: answer = 1000000000000
93 Correct 265 ms 49740 KB Correct answer: answer = 998762383161
94 Correct 313 ms 49908 KB Correct answer: answer = 23017412908
95 Correct 271 ms 49848 KB Correct answer: answer = 728143410622
96 Correct 259 ms 49804 KB Correct answer: answer = 2
97 Correct 305 ms 49888 KB Correct answer: answer = 1824916
98 Correct 306 ms 49896 KB Correct answer: answer = 10680029
99 Correct 300 ms 49900 KB Correct answer: answer = 18351700
100 Correct 289 ms 49984 KB Correct answer: answer = 16040026
101 Correct 270 ms 49840 KB Correct answer: answer = 253968628325
102 Correct 278 ms 49744 KB Correct answer: answer = 10267
103 Correct 307 ms 49980 KB Correct answer: answer = 2582408
104 Correct 258 ms 49840 KB Correct answer: answer = 78024964781
105 Correct 267 ms 49844 KB Correct answer: answer = 9866346457
106 Correct 276 ms 49840 KB Correct answer: answer = 3327720949
107 Correct 262 ms 49868 KB Correct answer: answer = 86064128360
108 Correct 279 ms 49848 KB Correct answer: answer = 12698259150
109 Correct 308 ms 49888 KB Correct answer: answer = 1185259288
110 Correct 272 ms 51872 KB Correct answer: answer = 999889968863
111 Correct 275 ms 51868 KB Correct answer: answer = 999861384931
112 Correct 273 ms 51888 KB Correct answer: answer = 999811809929
113 Correct 301 ms 51876 KB Correct answer: answer = 999869756441
114 Correct 588 ms 52408 KB Correct answer: answer = 1700000000
115 Correct 646 ms 52444 KB Correct answer: answer = 131666670
116 Correct 364 ms 50536 KB Correct answer: answer = 89478486
117 Correct 373 ms 50560 KB Correct answer: answer = 4971040
118 Correct 367 ms 50540 KB Correct answer: answer = 2711494
119 Correct 634 ms 52444 KB Correct answer: answer = 25252530
120 Correct 636 ms 52512 KB Correct answer: answer = 62500000
121 Correct 808 ms 52556 KB Correct answer: answer = 333175097780
122 Correct 833 ms 52552 KB Correct answer: answer = 33121180179
123 Correct 821 ms 52552 KB Correct answer: answer = 9802314015
124 Correct 622 ms 52440 KB Correct answer: answer = 32567551
125 Correct 716 ms 52496 KB Correct answer: answer = 997525000000
126 Correct 726 ms 52476 KB Correct answer: answer = 752723538884
127 Correct 268 ms 51836 KB Correct answer: answer = 1000000000000
128 Correct 272 ms 51904 KB Correct answer: answer = 999978000121
129 Correct 277 ms 51860 KB Correct answer: answer = 745986144735
130 Correct 278 ms 51492 KB Correct answer: answer = 2
131 Correct 713 ms 52484 KB Correct answer: answer = 277966670
132 Correct 656 ms 52532 KB Correct answer: answer = 2500900082
133 Correct 326 ms 51904 KB Correct answer: answer = 301248349636
134 Correct 461 ms 50988 KB Correct answer: answer = 14118891
135 Correct 277 ms 51880 KB Correct answer: answer = 14384977265
136 Correct 293 ms 51928 KB Correct answer: answer = 3681368330
137 Correct 294 ms 51904 KB Correct answer: answer = 2720316816
138 Correct 288 ms 54168 KB Correct answer: answer = 999976000144
139 Correct 296 ms 54176 KB Correct answer: answer = 999856102410
140 Correct 287 ms 54128 KB Correct answer: answer = 999958401531
141 Correct 310 ms 54204 KB Correct answer: answer = 999769649944
142 Correct 289 ms 54180 KB Correct answer: answer = 999874525918
143 Correct 976 ms 55428 KB Correct answer: answer = 6050000000
144 Correct 1027 ms 55452 KB Correct answer: answer = 1112500000
145 Correct 703 ms 53452 KB Correct answer: answer = 4294967296
146 Correct 801 ms 53552 KB Correct answer: answer = 87652406
147 Correct 767 ms 53460 KB Correct answer: answer = 6297664
148 Correct 814 ms 53452 KB Correct answer: answer = 196612
149 Correct 1061 ms 55460 KB Correct answer: answer = 15015100
150 Correct 1033 ms 55444 KB Correct answer: answer = 25000000
151 Correct 1209 ms 55536 KB Correct answer: answer = 333230209550
152 Correct 1218 ms 55528 KB Correct answer: answer = 917123769
153 Correct 1245 ms 55536 KB Correct answer: answer = 95162
154 Correct 1074 ms 55436 KB Correct answer: answer = 382616191
155 Correct 1155 ms 55600 KB Correct answer: answer = 990033333400
156 Correct 1130 ms 55484 KB Correct answer: answer = 990000100000
157 Correct 1098 ms 55320 KB Correct answer: answer = 749998188180
158 Correct 285 ms 54044 KB Correct answer: answer = 1000000000000
159 Correct 292 ms 54204 KB Correct answer: answer = 999988000036
160 Correct 300 ms 54144 KB Correct answer: answer = 744929274393
161 Correct 280 ms 53144 KB Correct answer: answer = 2
162 Correct 1145 ms 55424 KB Correct answer: answer = 1300024
163 Correct 1123 ms 55432 KB Correct answer: answer = 5000700010
164 Correct 398 ms 54440 KB Correct answer: answer = 354997100800
165 Correct 675 ms 52468 KB Correct answer: answer = 257000
166 Correct 817 ms 52648 KB Correct answer: answer = 3765323
167 Correct 746 ms 52548 KB Correct answer: answer = 1525903
168 Correct 292 ms 54204 KB Correct answer: answer = 67618137730
169 Correct 291 ms 54156 KB Correct answer: answer = 12656680171
170 Correct 334 ms 54204 KB Correct answer: answer = 579831736
171 Correct 626 ms 55036 KB Correct answer: answer = 23605611
172 Correct 372 ms 54184 KB Correct answer: answer = 7052481200
173 Correct 464 ms 54460 KB Correct answer: answer = 1314039500
174 Correct 556 ms 55032 KB Correct answer: answer = 302484000
175 Correct 1002 ms 54928 KB Correct answer: answer = 52348480