oj.uz

Submission #144493

# Submission time Handle Problem Language Result Execution time Memory
144493 2019-08-16T23:44:04 Z liwi Aliens (IOI16_aliens) C++11
100 / 100
 379 ms 6776 KB 
#include "aliens.h"

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;

#define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
char _;
#define complete_unique(a) a.erase(unique(a.begin(),a.end()),a.end())
#define all(a) a.begin(),a.end()
#define println printf("\n");
#define readln(x) getline(cin,x);
#define pb push_back
#define endl "\n"
#define INT_INF 0x3f3f3f3f
#define LL_INF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007
#define MOD2 1190492669
#define SEED 131
#define mp make_pair
#define fastio cin.tie(0); cin.sync_with_stdio(0);

#define MAXN 100005

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef unordered_map<int,int> umii;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef pair<int,pii> triple;
typedef int8_t byte;

mt19937 g1(time(0));

int randint(int a, int b){return uniform_int_distribution<int>(a, b)(g1);}
ll randlong(ll a,ll b){return uniform_int_distribution<long long>(a, b)(g1);}

ll gcd(ll a, ll b){return b == 0 ? a : gcd(b, a % b);}
ll lcm(ll a, ll b){return a*b/gcd(a,b);}
ll fpow(ll  b, ll exp, ll mod){if(exp == 0) return 1;ll t = fpow(b,exp/2,mod);if(exp&1) return t*t%mod*b%mod;return t*t%mod;}
ll divmod(ll i, ll j, ll mod){i%=mod,j%=mod;return i*fpow(j,mod-2,mod)%mod;}

int num_points,len,num_photo,ptr,cnt[MAXN],dq[MAXN],l,r;
pii points[MAXN],p[MAXN],lst;
ld dp[MAXN];
ll m[MAXN];

inline bool cmp(pii &a, pii &b){
	if(a.first == b.first) return a.second>b.second;
	return a.first<b.first;
}

inline ld calc(int i, int j){
	ld c1 = dp[j]+(ld)(p[i].second-p[j+1].first+1)*(p[i].second-p[j+1].first+1);
	ld c2 = m[j]*m[j];
	return c1-c2;
}

inline ld inter(int j, int k){
	ld m1 = (ld)-2.0*(p[j+1].first-1), b1 = (ld)(p[j+1].first-1)*(p[j+1].first-1)+dp[j]-m[j]*m[j];
	ld m2 = (ld)-2.0*(p[k+1].first-1), b2 = (ld)(p[k+1].first-1)*(p[k+1].first-1)+dp[k]-m[k]*m[k];
	return (ld)(b2-b1)/(m1-m2);
}

inline int getGroups(ld c){
	l = r = 1, dq[1] = 0;
	dp[0] = cnt[0] = 0;
	for(int i=1; i<=ptr; i++){
		while(r-l >= 1 && calc(i,dq[l]) >= calc(i,dq[l+1])) l++;
		dp[i] = calc(i,dq[l])+c;
		cnt[i] = cnt[dq[l]]+1;
		while(r-l >= 1 && inter(dq[r-1],i) <= inter(dq[r-1],dq[r])) r--;
		dq[++r] = i;
	}
	return cnt[ptr];
}

ll take_photos(int nn, int mm, int kk, vector<int> rows, vector<int> cols){
	num_points = nn, len = mm, num_photo = kk, ptr = 0;
	for(int i=1; i<=num_points; i++){
		int a = min(rows[i-1],cols[i-1]);
		int b = max(rows[i-1],cols[i-1]);
		points[i] = mp(a,b);
	}
	sort(points+1,points+num_points+1,cmp);
	lst = p[++ptr] = points[1], p[0] = mp(-1,-1);
	for(int i=2; i<=num_points; i++){
		int r = points[i].second;
		if(r > lst.second){
			p[++ptr] = points[i];
			lst = points[i];
		}
	}
	for(int i=1; i<ptr; i++)
		m[i] = max(0,p[i].second-p[i+1].first+1);
	memset(dp,0x3f,sizeof dp);
	ld low = 0, high = 1e12, ans = 0;
	while(high-low >= 1e-6){
		ld mid = (low+high)/2;
		if(getGroups(mid) <= num_photo){
			ans = mid;
			high = mid-1e-6;
		}else low = mid+1e-6;
	}
	getGroups(ans);
	ll res = round(dp[ptr]-ans*num_photo);
	return res;
}

Subtask #1
4.0 / 4.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
16.0 / 16.0

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

Subtask #5
19.0 / 19.0

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

Subtask #6
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1912 KB Correct answer: answer = 4
2 Correct 3 ms 1912 KB Correct answer: answer = 4
3 Correct 3 ms 1912 KB Correct answer: answer = 4
4 Correct 3 ms 1912 KB Correct answer: answer = 12
5 Correct 3 ms 1912 KB Correct answer: answer = 52
6 Correct 3 ms 1912 KB Correct answer: answer = 210
7 Correct 3 ms 1912 KB Correct answer: answer = 88
8 Correct 3 ms 1912 KB Correct answer: answer = 7696
9 Correct 3 ms 1912 KB Correct answer: answer = 1
10 Correct 3 ms 1912 KB Correct answer: answer = 2374
11 Correct 3 ms 1912 KB Correct answer: answer = 9502
12 Correct 3 ms 1784 KB Correct answer: answer = 49
13 Correct 3 ms 1912 KB Correct answer: answer = 151
14 Correct 3 ms 1912 KB Correct answer: answer = 7550
15 Correct 3 ms 1912 KB Correct answer: answer = 7220
16 Correct 3 ms 1916 KB Correct answer: answer = 7550
17 Correct 3 ms 1912 KB Correct answer: answer = 10000
18 Correct 3 ms 1912 KB Correct answer: answer = 10000
19 Correct 3 ms 1912 KB Correct answer: answer = 624
20 Correct 3 ms 1912 KB Correct answer: answer = 10000
21 Correct 4 ms 1912 KB Correct answer: answer = 1
22 Correct 3 ms 1912 KB Correct answer: answer = 4
23 Correct 3 ms 1912 KB Correct answer: answer = 1
24 Correct 3 ms 1912 KB Correct answer: answer = 5
25 Correct 3 ms 1912 KB Correct answer: answer = 41
26 Correct 3 ms 1912 KB Correct answer: answer = 71923
27 Correct 4 ms 1912 KB Correct answer: answer = 77137
28 Correct 4 ms 1912 KB Correct answer: answer = 764
29 Correct 4 ms 1912 KB Correct answer: answer = 250000
30 Correct 4 ms 1912 KB Correct answer: answer = 500
31 Correct 3 ms 1912 KB Correct answer: answer = 32
32 Correct 4 ms 1912 KB Correct answer: answer = 130050
33 Correct 4 ms 1912 KB Correct answer: answer = 5110
34 Correct 4 ms 1912 KB Correct answer: answer = 2626
35 Correct 4 ms 1912 KB Correct answer: answer = 796
36 Correct 5 ms 1912 KB Correct answer: answer = 7580
37 Correct 4 ms 1912 KB Correct answer: answer = 1904
38 Correct 4 ms 1912 KB Correct answer: answer = 996004
39 Correct 4 ms 1912 KB Correct answer: answer = 38817
40 Correct 4 ms 1912 KB Correct answer: answer = 4096
41 Correct 3 ms 1912 KB Correct answer: answer = 1
42 Correct 4 ms 1916 KB Correct answer: answer = 1
43 Correct 5 ms 1912 KB Correct answer: answer = 2040
44 Correct 3 ms 1912 KB Correct answer: answer = 2
45 Correct 3 ms 1912 KB Correct answer: answer = 4
46 Correct 3 ms 1912 KB Correct answer: answer = 9
47 Correct 4 ms 1912 KB Correct answer: answer = 9
48 Correct 4 ms 1912 KB Correct answer: answer = 21
49 Correct 4 ms 1912 KB Correct answer: answer = 71
50 Correct 3 ms 1912 KB Correct answer: answer = 77
51 Correct 4 ms 1912 KB Correct answer: answer = 400
52 Correct 4 ms 1884 KB Correct answer: answer = 996004
53 Correct 3 ms 1912 KB Correct answer: answer = 997310
54 Correct 4 ms 1884 KB Correct answer: answer = 990781
55 Correct 4 ms 1912 KB Correct answer: answer = 996545
56 Correct 3 ms 1912 KB Correct answer: answer = 484
57 Correct 4 ms 1956 KB Correct answer: answer = 484
58 Correct 5 ms 1912 KB Correct answer: answer = 63501
59 Correct 5 ms 1912 KB Correct answer: answer = 323501
60 Correct 5 ms 1912 KB Correct answer: answer = 752500
61 Correct 4 ms 1912 KB Correct answer: answer = 761480
62 Correct 5 ms 1912 KB Correct answer: answer = 758932
63 Correct 3 ms 1912 KB Correct answer: answer = 1000000
64 Correct 5 ms 1912 KB Correct answer: answer = 750500
65 Correct 4 ms 1912 KB Correct answer: answer = 1000000
66 Correct 4 ms 1912 KB Correct answer: answer = 250000
67 Correct 3 ms 1912 KB Correct answer: answer = 250000
68 Correct 4 ms 1912 KB Correct answer: answer = 1000000
69 Correct 4 ms 1912 KB Correct answer: answer = 994009
70 Correct 4 ms 1912 KB Correct answer: answer = 59315
71 Correct 4 ms 2040 KB Correct answer: answer = 25454
72 Correct 4 ms 1912 KB Correct answer: answer = 1504
73 Correct 3 ms 1912 KB Correct answer: answer = 37486
74 Correct 4 ms 1912 KB Correct answer: answer = 4284
75 Correct 3 ms 1912 KB Correct answer: answer = 158008
76 Correct 3 ms 1912 KB Correct answer: answer = 51860
77 Correct 4 ms 1912 KB Correct answer: answer = 12985
78 Correct 5 ms 2040 KB Correct answer: answer = 997864126212
79 Correct 5 ms 2040 KB Correct answer: answer = 998608411647
80 Correct 5 ms 2040 KB Correct answer: answer = 995265560477
81 Correct 14 ms 2128 KB Correct answer: answer = 10125000
82 Correct 13 ms 2040 KB Correct answer: answer = 2291668
83 Correct 9 ms 2040 KB Correct answer: answer = 42388
84 Correct 9 ms 2040 KB Correct answer: answer = 10318
85 Correct 8 ms 2044 KB Correct answer: answer = 3416
86 Correct 17 ms 2040 KB Correct answer: answer = 331708193881
87 Correct 18 ms 2044 KB Correct answer: answer = 2861193756
88 Correct 17 ms 2168 KB Correct answer: answer = 114646930
89 Correct 15 ms 2040 KB Correct answer: answer = 9280921
90 Correct 13 ms 2168 KB Correct answer: answer = 999984053400
91 Correct 17 ms 2040 KB Correct answer: answer = 750935949134
92 Correct 4 ms 2040 KB Correct answer: answer = 1000000000000
93 Correct 5 ms 2040 KB Correct answer: answer = 998762383161
94 Correct 17 ms 2040 KB Correct answer: answer = 23017412908
95 Correct 5 ms 2040 KB Correct answer: answer = 728143410622
96 Correct 4 ms 2040 KB Correct answer: answer = 2
97 Correct 13 ms 2040 KB Correct answer: answer = 1824916
98 Correct 14 ms 2040 KB Correct answer: answer = 10680029
99 Correct 14 ms 2168 KB Correct answer: answer = 18351700
100 Correct 13 ms 2168 KB Correct answer: answer = 16040026
101 Correct 6 ms 2040 KB Correct answer: answer = 253968628325
102 Correct 9 ms 2040 KB Correct answer: answer = 10267
103 Correct 13 ms 2168 KB Correct answer: answer = 2582408
104 Correct 5 ms 2040 KB Correct answer: answer = 78024964781
105 Correct 5 ms 2040 KB Correct answer: answer = 9866346457
106 Correct 6 ms 2040 KB Correct answer: answer = 3327720949
107 Correct 5 ms 2040 KB Correct answer: answer = 86064128360
108 Correct 6 ms 2040 KB Correct answer: answer = 12698259150
109 Correct 10 ms 2040 KB Correct answer: answer = 1185259288
110 Correct 24 ms 3108 KB Correct answer: answer = 999889968863
111 Correct 24 ms 3036 KB Correct answer: answer = 999861384931
112 Correct 24 ms 3192 KB Correct answer: answer = 999811809929
113 Correct 24 ms 3064 KB Correct answer: answer = 999869756441
114 Correct 127 ms 4088 KB Correct answer: answer = 1700000000
115 Correct 133 ms 4216 KB Correct answer: answer = 131666670
116 Correct 44 ms 2680 KB Correct answer: answer = 89478486
117 Correct 46 ms 2680 KB Correct answer: answer = 4971040
118 Correct 44 ms 2808 KB Correct answer: answer = 2711494
119 Correct 133 ms 4368 KB Correct answer: answer = 25252530
120 Correct 128 ms 4344 KB Correct answer: answer = 62500000
121 Correct 205 ms 3960 KB Correct answer: answer = 333175097780
122 Correct 189 ms 4088 KB Correct answer: answer = 33121180179
123 Correct 190 ms 4220 KB Correct answer: answer = 9802314015
124 Correct 136 ms 4236 KB Correct answer: answer = 32567551
125 Correct 136 ms 4344 KB Correct answer: answer = 997525000000
126 Correct 177 ms 3960 KB Correct answer: answer = 752723538884
127 Correct 19 ms 3064 KB Correct answer: answer = 1000000000000
128 Correct 23 ms 3064 KB Correct answer: answer = 999978000121
129 Correct 24 ms 3068 KB Correct answer: answer = 745986144735
130 Correct 13 ms 3064 KB Correct answer: answer = 2
131 Correct 133 ms 4220 KB Correct answer: answer = 277966670
132 Correct 122 ms 4092 KB Correct answer: answer = 2500900082
133 Correct 40 ms 3228 KB Correct answer: answer = 301248349636
134 Correct 94 ms 3064 KB Correct answer: answer = 14118891
135 Correct 24 ms 3072 KB Correct answer: answer = 14384977265
136 Correct 24 ms 3192 KB Correct answer: answer = 3681368330
137 Correct 25 ms 3192 KB Correct answer: answer = 2720316816
138 Correct 45 ms 4192 KB Correct answer: answer = 999976000144
139 Correct 45 ms 4216 KB Correct answer: answer = 999856102410
140 Correct 45 ms 4236 KB Correct answer: answer = 999958401531
141 Correct 45 ms 4216 KB Correct answer: answer = 999769649944
142 Correct 48 ms 4344 KB Correct answer: answer = 999874525918
143 Correct 260 ms 6456 KB Correct answer: answer = 6050000000
144 Correct 263 ms 6520 KB Correct answer: answer = 1112500000
145 Correct 160 ms 4956 KB Correct answer: answer = 4294967296
146 Correct 175 ms 5084 KB Correct answer: answer = 87652406
147 Correct 174 ms 5056 KB Correct answer: answer = 6297664
148 Correct 165 ms 4932 KB Correct answer: answer = 196612
149 Correct 265 ms 6660 KB Correct answer: answer = 15015100
150 Correct 252 ms 6648 KB Correct answer: answer = 25000000
151 Correct 361 ms 6136 KB Correct answer: answer = 333230209550
152 Correct 379 ms 6200 KB Correct answer: answer = 917123769
153 Correct 272 ms 6520 KB Correct answer: answer = 95162
154 Correct 265 ms 6776 KB Correct answer: answer = 382616191
155 Correct 264 ms 6776 KB Correct answer: answer = 990033333400
156 Correct 217 ms 6524 KB Correct answer: answer = 990000100000
157 Correct 284 ms 6136 KB Correct answer: answer = 749998188180
158 Correct 32 ms 4216 KB Correct answer: answer = 1000000000000
159 Correct 44 ms 4216 KB Correct answer: answer = 999988000036
160 Correct 44 ms 4316 KB Correct answer: answer = 744929274393
161 Correct 24 ms 4216 KB Correct answer: answer = 2
162 Correct 217 ms 6644 KB Correct answer: answer = 1300024
163 Correct 261 ms 6648 KB Correct answer: answer = 5000700010
164 Correct 79 ms 4472 KB Correct answer: answer = 354997100800
165 Correct 159 ms 4196 KB Correct answer: answer = 257000
166 Correct 149 ms 4216 KB Correct answer: answer = 3765323
167 Correct 155 ms 4344 KB Correct answer: answer = 1525903
168 Correct 44 ms 4344 KB Correct answer: answer = 67618137730
169 Correct 44 ms 4216 KB Correct answer: answer = 12656680171
170 Correct 51 ms 4316 KB Correct answer: answer = 579831736
171 Correct 124 ms 4984 KB Correct answer: answer = 23605611
172 Correct 50 ms 4344 KB Correct answer: answer = 7052481200
173 Correct 62 ms 4600 KB Correct answer: answer = 1314039500
174 Correct 78 ms 4728 KB Correct answer: answer = 302484000
175 Correct 167 ms 5508 KB Correct answer: answer = 52348480