oj.uz

Submission #290274

# Submission time Handle Problem Language Result Execution time Memory
290274 2020-09-03T15:02:04 Z shayan_p Aliens (IOI16_aliens) C++17
100 / 100
 446 ms 6380 KB 
#include<bits/stdc++.h>
#include "aliens.h"

#define F first
#define S second
#define PB push_back
#define sz(s) (int(s.size()))
#define bit(n, k) (((n)>>(k)) & 1)

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;

const int maxn = 1e5 + 10, mod = 1e9 + 7;
const ll inf = 1e13 + 10, INF = 1e18;

pll dp[maxn];
int mn[maxn];

struct CHT{
    deque<pair<pll, ll>> v;
    long double cross(pll a, pll b){
	//	a.F * x + a.S == b.F * x + b.S;
	return (long double)(b.S - a.S) / (a.F - b.F);
    }
    bool bad(pll a, pll b, pll c){
	long double A = cross(a, b), B = cross(b, c);
	return A < B;
    }
    pll eval(int id, ll x){
	return {v[id].F.F * x + v[id].F.S, v[id].S};	
    }
    void add(ll a, ll b, ll c){
	if(!v.empty() && v.back().F.F == a){
	    if(v.back().F.S < b)
		return;
	    if(v.back().F.S > b){
		v.pop_back();
	    }
	    else{
		if(v.back().S < c)
		    return;
		v.pop_back();
	    }
	}
	while(sz(v) > 1 && bad(v[sz(v)-2].F, v[sz(v)-1].F, {a, b}))
	    v.pop_back();
	while(sz(v) > 1 && cross(v[sz(v)-2].F, v[sz(v)-1].F) == cross(v[sz(v)-1].F, {a, b}) && v[sz(v)-1].S >= min(c, v[sz(v)-2].S))
	    v.pop_back();
	v.PB({{a, b}, c});
    }
    pll ask(ll x){
	while(sz(v) > 1 && eval(0, x) > eval(1, x))
	    v.pop_front();
	return eval(0, x);
    }
    void clear(){
	v.clear();
    }
};CHT cht;

pll solve(vector<pii> &seg, ll c){
    cht.clear();
    cht.add(seg[0].F, 1ll * seg[0].F * seg[0].F, 0);
    for(int i = 1; i <= sz(seg); i++){
	int mn = i == sz(seg) ? (seg[i-1].S + 1) : seg[i].F;
	mn = min(mn, seg[i-1].S + 1);
	dp[i] = cht.ask(-2 * (seg[i-1].S + 1));
	dp[i].F+= -1ll * mn * mn + 2ll * (seg[i-1].S + 1) * mn + c;
	dp[i].S++;
	if(i < sz(seg))
	    cht.add(seg[i].F, dp[i].F + 1ll * seg[i].F * seg[i].F, dp[i].S);
    }
    return dp[sz(seg)];
}
ll take_photos(int m, int n, int k, vector<int> X, vector<int> Y){
    vector<pii> _seg, seg;
    for(int i = 0; i < m; i++){
	if(X[i] > Y[i])
	    swap(X[i], Y[i]);
	_seg.PB({X[i], Y[i]});
    }
    sort(_seg.begin(), _seg.end());
    for(pii p : _seg){
	if(seg.empty() || seg.back().S < p.S)
	    seg.PB(p);
    }
    
    ll l = -1, r = inf;
    while(r-l > 1){
	ll mid = (l+r) >> 1;
	pll p = solve(seg, mid);
	if(p.S > k)
	    l = mid;
	else
	    r = mid;
    }
    pll p = solve(seg, r);
    return 1ll * p.F - 1ll * k * r;
}

Subtask #1
4.0 / 4.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
16.0 / 16.0

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

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Correct answer: answer = 4
2 Correct 0 ms 256 KB Correct answer: answer = 4
3 Correct 0 ms 256 KB Correct answer: answer = 4
4 Correct 0 ms 256 KB Correct answer: answer = 12
5 Correct 0 ms 308 KB Correct answer: answer = 52
6 Correct 0 ms 256 KB Correct answer: answer = 210
7 Correct 0 ms 256 KB Correct answer: answer = 88
8 Correct 0 ms 256 KB Correct answer: answer = 7696
9 Correct 0 ms 256 KB Correct answer: answer = 1
10 Correct 0 ms 384 KB Correct answer: answer = 2374
11 Correct 1 ms 384 KB Correct answer: answer = 9502
12 Correct 1 ms 256 KB Correct answer: answer = 49
13 Correct 0 ms 256 KB Correct answer: answer = 151
14 Correct 1 ms 384 KB Correct answer: answer = 7550
15 Correct 1 ms 256 KB Correct answer: answer = 7220
16 Correct 1 ms 256 KB Correct answer: answer = 7550
17 Correct 0 ms 256 KB Correct answer: answer = 10000
18 Correct 1 ms 256 KB Correct answer: answer = 10000
19 Correct 0 ms 384 KB Correct answer: answer = 624
20 Correct 0 ms 384 KB Correct answer: answer = 10000
21 Correct 0 ms 256 KB Correct answer: answer = 1
22 Correct 0 ms 256 KB Correct answer: answer = 4
23 Correct 0 ms 256 KB Correct answer: answer = 1
24 Correct 0 ms 256 KB Correct answer: answer = 5
25 Correct 0 ms 384 KB Correct answer: answer = 41
26 Correct 1 ms 256 KB Correct answer: answer = 71923
27 Correct 1 ms 384 KB Correct answer: answer = 77137
28 Correct 2 ms 384 KB Correct answer: answer = 764
29 Correct 2 ms 384 KB Correct answer: answer = 250000
30 Correct 2 ms 384 KB Correct answer: answer = 500
31 Correct 0 ms 256 KB Correct answer: answer = 32
32 Correct 2 ms 384 KB Correct answer: answer = 130050
33 Correct 2 ms 384 KB Correct answer: answer = 5110
34 Correct 1 ms 384 KB Correct answer: answer = 2626
35 Correct 1 ms 384 KB Correct answer: answer = 796
36 Correct 2 ms 384 KB Correct answer: answer = 7580
37 Correct 2 ms 384 KB Correct answer: answer = 1904
38 Correct 2 ms 384 KB Correct answer: answer = 996004
39 Correct 2 ms 384 KB Correct answer: answer = 38817
40 Correct 2 ms 384 KB Correct answer: answer = 4096
41 Correct 1 ms 384 KB Correct answer: answer = 1
42 Correct 1 ms 288 KB Correct answer: answer = 1
43 Correct 2 ms 384 KB Correct answer: answer = 2040
44 Correct 0 ms 384 KB Correct answer: answer = 2
45 Correct 1 ms 288 KB Correct answer: answer = 4
46 Correct 0 ms 256 KB Correct answer: answer = 9
47 Correct 1 ms 256 KB Correct answer: answer = 9
48 Correct 0 ms 256 KB Correct answer: answer = 21
49 Correct 0 ms 256 KB Correct answer: answer = 71
50 Correct 0 ms 256 KB Correct answer: answer = 77
51 Correct 1 ms 256 KB Correct answer: answer = 400
52 Correct 1 ms 384 KB Correct answer: answer = 996004
53 Correct 1 ms 384 KB Correct answer: answer = 997310
54 Correct 1 ms 384 KB Correct answer: answer = 990781
55 Correct 1 ms 384 KB Correct answer: answer = 996545
56 Correct 1 ms 384 KB Correct answer: answer = 484
57 Correct 1 ms 384 KB Correct answer: answer = 484
58 Correct 2 ms 384 KB Correct answer: answer = 63501
59 Correct 2 ms 384 KB Correct answer: answer = 323501
60 Correct 2 ms 384 KB Correct answer: answer = 752500
61 Correct 1 ms 384 KB Correct answer: answer = 761480
62 Correct 2 ms 384 KB Correct answer: answer = 758932
63 Correct 1 ms 384 KB Correct answer: answer = 1000000
64 Correct 2 ms 384 KB Correct answer: answer = 750500
65 Correct 1 ms 384 KB Correct answer: answer = 1000000
66 Correct 1 ms 384 KB Correct answer: answer = 250000
67 Correct 1 ms 384 KB Correct answer: answer = 250000
68 Correct 1 ms 384 KB Correct answer: answer = 1000000
69 Correct 1 ms 384 KB Correct answer: answer = 994009
70 Correct 1 ms 384 KB Correct answer: answer = 59315
71 Correct 1 ms 384 KB Correct answer: answer = 25454
72 Correct 1 ms 384 KB Correct answer: answer = 1504
73 Correct 1 ms 384 KB Correct answer: answer = 37486
74 Correct 1 ms 384 KB Correct answer: answer = 4284
75 Correct 1 ms 384 KB Correct answer: answer = 158008
76 Correct 1 ms 384 KB Correct answer: answer = 51860
77 Correct 1 ms 384 KB Correct answer: answer = 12985
78 Correct 2 ms 384 KB Correct answer: answer = 997864126212
79 Correct 2 ms 384 KB Correct answer: answer = 998608411647
80 Correct 2 ms 384 KB Correct answer: answer = 995265560477
81 Correct 13 ms 512 KB Correct answer: answer = 10125000
82 Correct 14 ms 512 KB Correct answer: answer = 2291668
83 Correct 7 ms 384 KB Correct answer: answer = 42388
84 Correct 7 ms 384 KB Correct answer: answer = 10318
85 Correct 7 ms 416 KB Correct answer: answer = 3416
86 Correct 19 ms 512 KB Correct answer: answer = 331708193881
87 Correct 17 ms 512 KB Correct answer: answer = 2861193756
88 Correct 15 ms 512 KB Correct answer: answer = 114646930
89 Correct 13 ms 512 KB Correct answer: answer = 9280921
90 Correct 13 ms 512 KB Correct answer: answer = 999984053400
91 Correct 15 ms 512 KB Correct answer: answer = 750935949134
92 Correct 2 ms 384 KB Correct answer: answer = 1000000000000
93 Correct 3 ms 384 KB Correct answer: answer = 998762383161
94 Correct 17 ms 512 KB Correct answer: answer = 23017412908
95 Correct 3 ms 384 KB Correct answer: answer = 728143410622
96 Correct 2 ms 384 KB Correct answer: answer = 2
97 Correct 13 ms 512 KB Correct answer: answer = 1824916
98 Correct 15 ms 512 KB Correct answer: answer = 10680029
99 Correct 15 ms 512 KB Correct answer: answer = 18351700
100 Correct 14 ms 512 KB Correct answer: answer = 16040026
101 Correct 3 ms 512 KB Correct answer: answer = 253968628325
102 Correct 8 ms 488 KB Correct answer: answer = 10267
103 Correct 14 ms 512 KB Correct answer: answer = 2582408
104 Correct 2 ms 384 KB Correct answer: answer = 78024964781
105 Correct 2 ms 384 KB Correct answer: answer = 9866346457
106 Correct 4 ms 416 KB Correct answer: answer = 3327720949
107 Correct 2 ms 384 KB Correct answer: answer = 86064128360
108 Correct 4 ms 512 KB Correct answer: answer = 12698259150
109 Correct 11 ms 512 KB Correct answer: answer = 1185259288
110 Correct 21 ms 1788 KB Correct answer: answer = 999889968863
111 Correct 21 ms 1916 KB Correct answer: answer = 999861384931
112 Correct 22 ms 1788 KB Correct answer: answer = 999811809929
113 Correct 21 ms 1788 KB Correct answer: answer = 999869756441
114 Correct 158 ms 3184 KB Correct answer: answer = 1700000000
115 Correct 190 ms 3184 KB Correct answer: answer = 131666670
116 Correct 52 ms 1280 KB Correct answer: answer = 89478486
117 Correct 56 ms 1400 KB Correct answer: answer = 4971040
118 Correct 56 ms 1280 KB Correct answer: answer = 2711494
119 Correct 173 ms 3440 KB Correct answer: answer = 25252530
120 Correct 175 ms 3292 KB Correct answer: answer = 62500000
121 Correct 236 ms 2808 KB Correct answer: answer = 333175097780
122 Correct 237 ms 2808 KB Correct answer: answer = 33121180179
123 Correct 226 ms 2808 KB Correct answer: answer = 9802314015
124 Correct 170 ms 3312 KB Correct answer: answer = 32567551
125 Correct 174 ms 3312 KB Correct answer: answer = 997525000000
126 Correct 199 ms 2960 KB Correct answer: answer = 752723538884
127 Correct 14 ms 1788 KB Correct answer: answer = 1000000000000
128 Correct 20 ms 1788 KB Correct answer: answer = 999978000121
129 Correct 22 ms 1788 KB Correct answer: answer = 745986144735
130 Correct 11 ms 1788 KB Correct answer: answer = 2
131 Correct 177 ms 3316 KB Correct answer: answer = 277966670
132 Correct 148 ms 3312 KB Correct answer: answer = 2500900082
133 Correct 45 ms 1788 KB Correct answer: answer = 301248349636
134 Correct 96 ms 1780 KB Correct answer: answer = 14118891
135 Correct 21 ms 1788 KB Correct answer: answer = 14384977265
136 Correct 22 ms 1788 KB Correct answer: answer = 3681368330
137 Correct 22 ms 1788 KB Correct answer: answer = 2720316816

Subtask #6
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Correct answer: answer = 4
2 Correct 0 ms 256 KB Correct answer: answer = 4
3 Correct 0 ms 256 KB Correct answer: answer = 4
4 Correct 0 ms 256 KB Correct answer: answer = 12
5 Correct 0 ms 308 KB Correct answer: answer = 52
6 Correct 0 ms 256 KB Correct answer: answer = 210
7 Correct 0 ms 256 KB Correct answer: answer = 88
8 Correct 0 ms 256 KB Correct answer: answer = 7696
9 Correct 0 ms 256 KB Correct answer: answer = 1
10 Correct 0 ms 384 KB Correct answer: answer = 2374
11 Correct 1 ms 384 KB Correct answer: answer = 9502
12 Correct 1 ms 256 KB Correct answer: answer = 49
13 Correct 0 ms 256 KB Correct answer: answer = 151
14 Correct 1 ms 384 KB Correct answer: answer = 7550
15 Correct 1 ms 256 KB Correct answer: answer = 7220
16 Correct 1 ms 256 KB Correct answer: answer = 7550
17 Correct 0 ms 256 KB Correct answer: answer = 10000
18 Correct 1 ms 256 KB Correct answer: answer = 10000
19 Correct 0 ms 384 KB Correct answer: answer = 624
20 Correct 0 ms 384 KB Correct answer: answer = 10000
21 Correct 0 ms 256 KB Correct answer: answer = 1
22 Correct 0 ms 256 KB Correct answer: answer = 4
23 Correct 0 ms 256 KB Correct answer: answer = 1
24 Correct 0 ms 256 KB Correct answer: answer = 5
25 Correct 0 ms 384 KB Correct answer: answer = 41
26 Correct 1 ms 256 KB Correct answer: answer = 71923
27 Correct 1 ms 384 KB Correct answer: answer = 77137
28 Correct 2 ms 384 KB Correct answer: answer = 764
29 Correct 2 ms 384 KB Correct answer: answer = 250000
30 Correct 2 ms 384 KB Correct answer: answer = 500
31 Correct 0 ms 256 KB Correct answer: answer = 32
32 Correct 2 ms 384 KB Correct answer: answer = 130050
33 Correct 2 ms 384 KB Correct answer: answer = 5110
34 Correct 1 ms 384 KB Correct answer: answer = 2626
35 Correct 1 ms 384 KB Correct answer: answer = 796
36 Correct 2 ms 384 KB Correct answer: answer = 7580
37 Correct 2 ms 384 KB Correct answer: answer = 1904
38 Correct 2 ms 384 KB Correct answer: answer = 996004
39 Correct 2 ms 384 KB Correct answer: answer = 38817
40 Correct 2 ms 384 KB Correct answer: answer = 4096
41 Correct 1 ms 384 KB Correct answer: answer = 1
42 Correct 1 ms 288 KB Correct answer: answer = 1
43 Correct 2 ms 384 KB Correct answer: answer = 2040
44 Correct 0 ms 384 KB Correct answer: answer = 2
45 Correct 1 ms 288 KB Correct answer: answer = 4
46 Correct 0 ms 256 KB Correct answer: answer = 9
47 Correct 1 ms 256 KB Correct answer: answer = 9
48 Correct 0 ms 256 KB Correct answer: answer = 21
49 Correct 0 ms 256 KB Correct answer: answer = 71
50 Correct 0 ms 256 KB Correct answer: answer = 77
51 Correct 1 ms 256 KB Correct answer: answer = 400
52 Correct 1 ms 384 KB Correct answer: answer = 996004
53 Correct 1 ms 384 KB Correct answer: answer = 997310
54 Correct 1 ms 384 KB Correct answer: answer = 990781
55 Correct 1 ms 384 KB Correct answer: answer = 996545
56 Correct 1 ms 384 KB Correct answer: answer = 484
57 Correct 1 ms 384 KB Correct answer: answer = 484
58 Correct 2 ms 384 KB Correct answer: answer = 63501
59 Correct 2 ms 384 KB Correct answer: answer = 323501
60 Correct 2 ms 384 KB Correct answer: answer = 752500
61 Correct 1 ms 384 KB Correct answer: answer = 761480
62 Correct 2 ms 384 KB Correct answer: answer = 758932
63 Correct 1 ms 384 KB Correct answer: answer = 1000000
64 Correct 2 ms 384 KB Correct answer: answer = 750500
65 Correct 1 ms 384 KB Correct answer: answer = 1000000
66 Correct 1 ms 384 KB Correct answer: answer = 250000
67 Correct 1 ms 384 KB Correct answer: answer = 250000
68 Correct 1 ms 384 KB Correct answer: answer = 1000000
69 Correct 1 ms 384 KB Correct answer: answer = 994009
70 Correct 1 ms 384 KB Correct answer: answer = 59315
71 Correct 1 ms 384 KB Correct answer: answer = 25454
72 Correct 1 ms 384 KB Correct answer: answer = 1504
73 Correct 1 ms 384 KB Correct answer: answer = 37486
74 Correct 1 ms 384 KB Correct answer: answer = 4284
75 Correct 1 ms 384 KB Correct answer: answer = 158008
76 Correct 1 ms 384 KB Correct answer: answer = 51860
77 Correct 1 ms 384 KB Correct answer: answer = 12985
78 Correct 2 ms 384 KB Correct answer: answer = 997864126212
79 Correct 2 ms 384 KB Correct answer: answer = 998608411647
80 Correct 2 ms 384 KB Correct answer: answer = 995265560477
81 Correct 13 ms 512 KB Correct answer: answer = 10125000
82 Correct 14 ms 512 KB Correct answer: answer = 2291668
83 Correct 7 ms 384 KB Correct answer: answer = 42388
84 Correct 7 ms 384 KB Correct answer: answer = 10318
85 Correct 7 ms 416 KB Correct answer: answer = 3416
86 Correct 19 ms 512 KB Correct answer: answer = 331708193881
87 Correct 17 ms 512 KB Correct answer: answer = 2861193756
88 Correct 15 ms 512 KB Correct answer: answer = 114646930
89 Correct 13 ms 512 KB Correct answer: answer = 9280921
90 Correct 13 ms 512 KB Correct answer: answer = 999984053400
91 Correct 15 ms 512 KB Correct answer: answer = 750935949134
92 Correct 2 ms 384 KB Correct answer: answer = 1000000000000
93 Correct 3 ms 384 KB Correct answer: answer = 998762383161
94 Correct 17 ms 512 KB Correct answer: answer = 23017412908
95 Correct 3 ms 384 KB Correct answer: answer = 728143410622
96 Correct 2 ms 384 KB Correct answer: answer = 2
97 Correct 13 ms 512 KB Correct answer: answer = 1824916
98 Correct 15 ms 512 KB Correct answer: answer = 10680029
99 Correct 15 ms 512 KB Correct answer: answer = 18351700
100 Correct 14 ms 512 KB Correct answer: answer = 16040026
101 Correct 3 ms 512 KB Correct answer: answer = 253968628325
102 Correct 8 ms 488 KB Correct answer: answer = 10267
103 Correct 14 ms 512 KB Correct answer: answer = 2582408
104 Correct 2 ms 384 KB Correct answer: answer = 78024964781
105 Correct 2 ms 384 KB Correct answer: answer = 9866346457
106 Correct 4 ms 416 KB Correct answer: answer = 3327720949
107 Correct 2 ms 384 KB Correct answer: answer = 86064128360
108 Correct 4 ms 512 KB Correct answer: answer = 12698259150
109 Correct 11 ms 512 KB Correct answer: answer = 1185259288
110 Correct 21 ms 1788 KB Correct answer: answer = 999889968863
111 Correct 21 ms 1916 KB Correct answer: answer = 999861384931
112 Correct 22 ms 1788 KB Correct answer: answer = 999811809929
113 Correct 21 ms 1788 KB Correct answer: answer = 999869756441
114 Correct 158 ms 3184 KB Correct answer: answer = 1700000000
115 Correct 190 ms 3184 KB Correct answer: answer = 131666670
116 Correct 52 ms 1280 KB Correct answer: answer = 89478486
117 Correct 56 ms 1400 KB Correct answer: answer = 4971040
118 Correct 56 ms 1280 KB Correct answer: answer = 2711494
119 Correct 173 ms 3440 KB Correct answer: answer = 25252530
120 Correct 175 ms 3292 KB Correct answer: answer = 62500000
121 Correct 236 ms 2808 KB Correct answer: answer = 333175097780
122 Correct 237 ms 2808 KB Correct answer: answer = 33121180179
123 Correct 226 ms 2808 KB Correct answer: answer = 9802314015
124 Correct 170 ms 3312 KB Correct answer: answer = 32567551
125 Correct 174 ms 3312 KB Correct answer: answer = 997525000000
126 Correct 199 ms 2960 KB Correct answer: answer = 752723538884
127 Correct 14 ms 1788 KB Correct answer: answer = 1000000000000
128 Correct 20 ms 1788 KB Correct answer: answer = 999978000121
129 Correct 22 ms 1788 KB Correct answer: answer = 745986144735
130 Correct 11 ms 1788 KB Correct answer: answer = 2
131 Correct 177 ms 3316 KB Correct answer: answer = 277966670
132 Correct 148 ms 3312 KB Correct answer: answer = 2500900082
133 Correct 45 ms 1788 KB Correct answer: answer = 301248349636
134 Correct 96 ms 1780 KB Correct answer: answer = 14118891
135 Correct 21 ms 1788 KB Correct answer: answer = 14384977265
136 Correct 22 ms 1788 KB Correct answer: answer = 3681368330
137 Correct 22 ms 1788 KB Correct answer: answer = 2720316816
138 Correct 43 ms 3064 KB Correct answer: answer = 999976000144
139 Correct 43 ms 3088 KB Correct answer: answer = 999856102410
140 Correct 42 ms 3064 KB Correct answer: answer = 999958401531
141 Correct 42 ms 3064 KB Correct answer: answer = 999769649944
142 Correct 41 ms 3056 KB Correct answer: answer = 999874525918
143 Correct 344 ms 5996 KB Correct answer: answer = 6050000000
144 Correct 365 ms 5992 KB Correct answer: answer = 1112500000
145 Correct 203 ms 4208 KB Correct answer: answer = 4294967296
146 Correct 235 ms 4208 KB Correct answer: answer = 87652406
147 Correct 240 ms 4208 KB Correct answer: answer = 6297664
148 Correct 224 ms 4204 KB Correct answer: answer = 196612
149 Correct 356 ms 6236 KB Correct answer: answer = 15015100
150 Correct 350 ms 6380 KB Correct answer: answer = 25000000
151 Correct 436 ms 5168 KB Correct answer: answer = 333230209550
152 Correct 446 ms 5076 KB Correct answer: answer = 917123769
153 Correct 368 ms 4996 KB Correct answer: answer = 95162
154 Correct 371 ms 6320 KB Correct answer: answer = 382616191
155 Correct 352 ms 6252 KB Correct answer: answer = 990033333400
156 Correct 343 ms 6380 KB Correct answer: answer = 990000100000
157 Correct 388 ms 4972 KB Correct answer: answer = 749998188180
158 Correct 28 ms 3056 KB Correct answer: answer = 1000000000000
159 Correct 42 ms 3056 KB Correct answer: answer = 999988000036
160 Correct 42 ms 3064 KB Correct answer: answer = 744929274393
161 Correct 22 ms 3064 KB Correct answer: answer = 2
162 Correct 331 ms 6252 KB Correct answer: answer = 1300024
163 Correct 342 ms 6252 KB Correct answer: answer = 5000700010
164 Correct 86 ms 3180 KB Correct answer: answer = 354997100800
165 Correct 200 ms 2928 KB Correct answer: answer = 257000
166 Correct 191 ms 3568 KB Correct answer: answer = 3765323
167 Correct 183 ms 3436 KB Correct answer: answer = 1525903
168 Correct 41 ms 3056 KB Correct answer: answer = 67618137730
169 Correct 42 ms 3064 KB Correct answer: answer = 12656680171
170 Correct 51 ms 3056 KB Correct answer: answer = 579831736
171 Correct 151 ms 3948 KB Correct answer: answer = 23605611
172 Correct 51 ms 3056 KB Correct answer: answer = 7052481200
173 Correct 88 ms 3056 KB Correct answer: answer = 1314039500
174 Correct 100 ms 3468 KB Correct answer: answer = 302484000
175 Correct 240 ms 4588 KB Correct answer: answer = 52348480