oj.uz

Submission #941990

# Submission time Handle Problem Language Result Execution time Memory
941990 2024-03-09T22:53:22 Z Edu175 Aliens (IOI16_aliens) C++17
100 / 100
 384 ms 10652 KB 
#include "aliens.h"
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(ll i=a,ggdem=b;i<ggdem;++i)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define imp(v) for(auto messi:v)cout<<messi<<" "; cout<<"\n"
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;

#define bint __int128

const ll INF=2e12;
ll sq(ll n){return n*n;}
vector<ii>a;
ll sup(ll i){
	//cerr<<"sup "<<i<<": "<<(!i?0:sq(max(a[i-1].snd-a[i].fst,(ll)0)))<<"\n";
	return (!i?0:sq(max(a[i-1].snd-a[i].fst,(ll)0)));
}
const ll MAXN=1e5+5;
ll dp[MAXN],cnt[MAXN];
//(min, increasing insert coefficents, non increasing queries, online) 
//for maximum just change the sign of lines
bint idiv(bint a, bint b){ //int division
	if((a<0)^(b<0))return (a+b-1)/b; //ceil
	return a/b; //floor
}
struct ln{
	bint a,b,i;
	bint eq(bint x){return a*x+b;}
	pair<bint,bint> operator%(ln l){
		bint x=idiv(b-l.b,l.a-a);
		return {x,eq(x)};
	}
};
deque<ln>cht;
ii query(bint x){
	ln l=cht.back(); cht.pop_back();
	while(SZ(cht)&&l.eq(x)>=cht.back().eq(x))l=cht.back(),cht.pop_back();
	cht.pb(l);
	//cout<<"query "<<(ll)cht.back().eq(x)<<" --> "<<(ll)cht.back().eq(x)/MAXN<<" or "<<ll(cht.back().eq(x)-cnt[cht.back().i])/MAXN<<"\n";
	ll idx=cht.back().i;
	return {(cht.back().eq(x)-cnt[idx])/MAXN,idx};
}
void insert(ln l){
	l.a*=MAXN,l.b=l.b*MAXN+cnt[l.i];
	if(!SZ(cht)){
		cht.pb(l);
		return;
	}
	ln m=cht.front(); cht.pop_front();
	while(SZ(cht)&&((l%m).fst>(m%cht.front()).fst||l%m==m%cht.front()))
		m=cht.front(),cht.pop_front();
	cht.push_front(m), cht.push_front(l);
}
void f(ll n, ll d){
	cht.clear();
	//cout<<"f "<<d<<":\n";
	for(ll i=n-1;i>=0;i--){
		insert(ln({-2*a[i].snd,sq(a[i].snd)+dp[i+1],i+1}));
		ll &res=dp[i];
		ii rq=query(a[i].fst);
		//cout<<rq.fst<<"\n";
		res=rq.fst+sq(a[i].fst)-sup(i)+d;
		cnt[i]=cnt[rq.snd]+1;
		//cout<<i<<": ("<<rq.snd<<") "<<dp[i]<<" "<<cnt[i]<<"\n";
	}
	//cout<<cnt[0]<<"\n\n";
	//cerr<<d<<" "<<cnt[0]<<"\n";
}
long long take_photos(int n, int m, int k, std::vector<int> R, std::vector<int> C) {
	vector<ii>a_;
	fore(i,0,n){
		ll l=R[i],r=C[i];
		if(l>r)swap(l,r);
		r++;
		a.pb({l,-r});
	}
	sort(ALL(a));
	//for(auto i:a)cout<<i.fst<<","<<i.snd<<" ";;cout<<"\n";;
	ll r=0;
	for(auto [s,e]:a){
		e=-e;
		if(e>r)a_.pb({s,e}),r=e;
	}
	a=a_;
	n=SZ(a);
	f(n,0);
	//cerr<<"dp_0 "<<dp[0]<<"\n";
	//for(auto i:a)cerr<<i.fst<<","<<i.snd<<" ";;cout<<"\n";
	ll l=0; r=1e13;
	while(l<=r){
		ll m=(l+r)/2;
		f(n,m);
		if(cnt[0]<=k)r=m-1;
		else l=m+1;
	}
	//cout<<n<<" "<<k<<"\n";
	//cout<<l<<"\n";
	f(n,l+1);
	f(n,l);
	//cerr<<k<<"\n";
	ll res=dp[0]-l*k;
	//cout<<cnt[0]<<"\n";
	return res;
}

Subtask #1
4.0 / 4.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
16.0 / 16.0

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

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct answer: answer = 4
2 Correct 0 ms 348 KB Correct answer: answer = 4
3 Correct 0 ms 348 KB Correct answer: answer = 4
4 Correct 0 ms 348 KB Correct answer: answer = 12
5 Correct 0 ms 344 KB Correct answer: answer = 52
6 Correct 0 ms 348 KB Correct answer: answer = 210
7 Correct 1 ms 348 KB Correct answer: answer = 88
8 Correct 0 ms 348 KB Correct answer: answer = 7696
9 Correct 0 ms 348 KB Correct answer: answer = 1
10 Correct 1 ms 348 KB Correct answer: answer = 2374
11 Correct 0 ms 348 KB Correct answer: answer = 9502
12 Correct 0 ms 348 KB Correct answer: answer = 49
13 Correct 1 ms 348 KB Correct answer: answer = 151
14 Correct 1 ms 348 KB Correct answer: answer = 7550
15 Correct 1 ms 444 KB Correct answer: answer = 7220
16 Correct 0 ms 348 KB Correct answer: answer = 7550
17 Correct 0 ms 348 KB Correct answer: answer = 10000
18 Correct 0 ms 348 KB Correct answer: answer = 10000
19 Correct 0 ms 348 KB Correct answer: answer = 624
20 Correct 0 ms 348 KB Correct answer: answer = 10000
21 Correct 0 ms 348 KB Correct answer: answer = 1
22 Correct 0 ms 348 KB Correct answer: answer = 4
23 Correct 0 ms 348 KB Correct answer: answer = 1
24 Correct 0 ms 348 KB Correct answer: answer = 5
25 Correct 1 ms 504 KB Correct answer: answer = 41
26 Correct 0 ms 348 KB Correct answer: answer = 71923
27 Correct 1 ms 348 KB Correct answer: answer = 77137
28 Correct 2 ms 348 KB Correct answer: answer = 764
29 Correct 2 ms 348 KB Correct answer: answer = 250000
30 Correct 2 ms 348 KB Correct answer: answer = 500
31 Correct 0 ms 348 KB Correct answer: answer = 32
32 Correct 2 ms 364 KB Correct answer: answer = 130050
33 Correct 2 ms 348 KB Correct answer: answer = 5110
34 Correct 1 ms 348 KB Correct answer: answer = 2626
35 Correct 1 ms 348 KB Correct answer: answer = 796
36 Correct 2 ms 348 KB Correct answer: answer = 7580
37 Correct 2 ms 348 KB Correct answer: answer = 1904
38 Correct 1 ms 348 KB Correct answer: answer = 996004
39 Correct 2 ms 348 KB Correct answer: answer = 38817
40 Correct 2 ms 348 KB Correct answer: answer = 4096
41 Correct 1 ms 348 KB Correct answer: answer = 1
42 Correct 1 ms 348 KB Correct answer: answer = 1
43 Correct 2 ms 348 KB Correct answer: answer = 2040
44 Correct 0 ms 348 KB Correct answer: answer = 2
45 Correct 0 ms 348 KB Correct answer: answer = 4
46 Correct 1 ms 348 KB Correct answer: answer = 9
47 Correct 0 ms 348 KB Correct answer: answer = 9
48 Correct 0 ms 348 KB Correct answer: answer = 21
49 Correct 0 ms 344 KB Correct answer: answer = 71
50 Correct 0 ms 348 KB Correct answer: answer = 77
51 Correct 1 ms 440 KB Correct answer: answer = 400
52 Correct 0 ms 348 KB Correct answer: answer = 996004
53 Correct 1 ms 344 KB Correct answer: answer = 997310
54 Correct 0 ms 348 KB Correct answer: answer = 990781
55 Correct 0 ms 348 KB Correct answer: answer = 996545
56 Correct 1 ms 348 KB Correct answer: answer = 484
57 Correct 1 ms 348 KB Correct answer: answer = 484
58 Correct 2 ms 348 KB Correct answer: answer = 63501
59 Correct 2 ms 348 KB Correct answer: answer = 323501
60 Correct 2 ms 348 KB Correct answer: answer = 752500
61 Correct 1 ms 448 KB Correct answer: answer = 761480
62 Correct 2 ms 348 KB Correct answer: answer = 758932
63 Correct 0 ms 348 KB Correct answer: answer = 1000000
64 Correct 2 ms 348 KB Correct answer: answer = 750500
65 Correct 0 ms 348 KB Correct answer: answer = 1000000
66 Correct 1 ms 344 KB Correct answer: answer = 250000
67 Correct 1 ms 348 KB Correct answer: answer = 250000
68 Correct 1 ms 348 KB Correct answer: answer = 1000000
69 Correct 0 ms 348 KB Correct answer: answer = 994009
70 Correct 1 ms 600 KB Correct answer: answer = 59315
71 Correct 2 ms 348 KB Correct answer: answer = 25454
72 Correct 2 ms 484 KB Correct answer: answer = 1504
73 Correct 1 ms 348 KB Correct answer: answer = 37486
74 Correct 1 ms 348 KB Correct answer: answer = 4284
75 Correct 1 ms 348 KB Correct answer: answer = 158008
76 Correct 1 ms 348 KB Correct answer: answer = 51860
77 Correct 1 ms 348 KB Correct answer: answer = 12985
78 Correct 1 ms 604 KB Correct answer: answer = 997864126212
79 Correct 1 ms 604 KB Correct answer: answer = 998608411647
80 Correct 1 ms 528 KB Correct answer: answer = 995265560477
81 Correct 12 ms 856 KB Correct answer: answer = 10125000
82 Correct 11 ms 604 KB Correct answer: answer = 2291668
83 Correct 6 ms 604 KB Correct answer: answer = 42388
84 Correct 7 ms 604 KB Correct answer: answer = 10318
85 Correct 6 ms 512 KB Correct answer: answer = 3416
86 Correct 17 ms 604 KB Correct answer: answer = 331708193881
87 Correct 18 ms 608 KB Correct answer: answer = 2861193756
88 Correct 16 ms 604 KB Correct answer: answer = 114646930
89 Correct 11 ms 600 KB Correct answer: answer = 9280921
90 Correct 11 ms 600 KB Correct answer: answer = 999984053400
91 Correct 14 ms 824 KB Correct answer: answer = 750935949134
92 Correct 1 ms 604 KB Correct answer: answer = 1000000000000
93 Correct 1 ms 604 KB Correct answer: answer = 998762383161
94 Correct 15 ms 604 KB Correct answer: answer = 23017412908
95 Correct 2 ms 604 KB Correct answer: answer = 728143410622
96 Correct 1 ms 604 KB Correct answer: answer = 2
97 Correct 11 ms 604 KB Correct answer: answer = 1824916
98 Correct 14 ms 604 KB Correct answer: answer = 10680029
99 Correct 13 ms 604 KB Correct answer: answer = 18351700
100 Correct 11 ms 840 KB Correct answer: answer = 16040026
101 Correct 3 ms 604 KB Correct answer: answer = 253968628325
102 Correct 6 ms 616 KB Correct answer: answer = 10267
103 Correct 13 ms 604 KB Correct answer: answer = 2582408
104 Correct 1 ms 528 KB Correct answer: answer = 78024964781
105 Correct 2 ms 604 KB Correct answer: answer = 9866346457
106 Correct 3 ms 704 KB Correct answer: answer = 3327720949
107 Correct 2 ms 604 KB Correct answer: answer = 86064128360
108 Correct 3 ms 604 KB Correct answer: answer = 12698259150
109 Correct 10 ms 604 KB Correct answer: answer = 1185259288
110 Correct 13 ms 3132 KB Correct answer: answer = 999889968863
111 Correct 13 ms 3032 KB Correct answer: answer = 999861384931
112 Correct 12 ms 3024 KB Correct answer: answer = 999811809929
113 Correct 12 ms 3028 KB Correct answer: answer = 999869756441
114 Correct 136 ms 5644 KB Correct answer: answer = 1700000000
115 Correct 141 ms 5188 KB Correct answer: answer = 131666670
116 Correct 44 ms 1884 KB Correct answer: answer = 89478486
117 Correct 46 ms 1860 KB Correct answer: answer = 4971040
118 Correct 44 ms 1884 KB Correct answer: answer = 2711494
119 Correct 137 ms 5196 KB Correct answer: answer = 25252530
120 Correct 148 ms 5392 KB Correct answer: answer = 62500000
121 Correct 203 ms 4176 KB Correct answer: answer = 333175097780
122 Correct 193 ms 4348 KB Correct answer: answer = 33121180179
123 Correct 180 ms 4180 KB Correct answer: answer = 9802314015
124 Correct 145 ms 5296 KB Correct answer: answer = 32567551
125 Correct 137 ms 5444 KB Correct answer: answer = 997525000000
126 Correct 165 ms 4240 KB Correct answer: answer = 752723538884
127 Correct 9 ms 2772 KB Correct answer: answer = 1000000000000
128 Correct 12 ms 3024 KB Correct answer: answer = 999978000121
129 Correct 14 ms 3028 KB Correct answer: answer = 745986144735
130 Correct 8 ms 2516 KB Correct answer: answer = 2
131 Correct 144 ms 5388 KB Correct answer: answer = 277966670
132 Correct 126 ms 5296 KB Correct answer: answer = 2500900082
133 Correct 31 ms 2768 KB Correct answer: answer = 301248349636
134 Correct 80 ms 2576 KB Correct answer: answer = 14118891
135 Correct 13 ms 3028 KB Correct answer: answer = 14384977265
136 Correct 14 ms 3024 KB Correct answer: answer = 3681368330
137 Correct 14 ms 3028 KB Correct answer: answer = 2720316816

Subtask #6
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct answer: answer = 4
2 Correct 0 ms 348 KB Correct answer: answer = 4
3 Correct 0 ms 348 KB Correct answer: answer = 4
4 Correct 0 ms 348 KB Correct answer: answer = 12
5 Correct 0 ms 344 KB Correct answer: answer = 52
6 Correct 0 ms 348 KB Correct answer: answer = 210
7 Correct 1 ms 348 KB Correct answer: answer = 88
8 Correct 0 ms 348 KB Correct answer: answer = 7696
9 Correct 0 ms 348 KB Correct answer: answer = 1
10 Correct 1 ms 348 KB Correct answer: answer = 2374
11 Correct 0 ms 348 KB Correct answer: answer = 9502
12 Correct 0 ms 348 KB Correct answer: answer = 49
13 Correct 1 ms 348 KB Correct answer: answer = 151
14 Correct 1 ms 348 KB Correct answer: answer = 7550
15 Correct 1 ms 444 KB Correct answer: answer = 7220
16 Correct 0 ms 348 KB Correct answer: answer = 7550
17 Correct 0 ms 348 KB Correct answer: answer = 10000
18 Correct 0 ms 348 KB Correct answer: answer = 10000
19 Correct 0 ms 348 KB Correct answer: answer = 624
20 Correct 0 ms 348 KB Correct answer: answer = 10000
21 Correct 0 ms 348 KB Correct answer: answer = 1
22 Correct 0 ms 348 KB Correct answer: answer = 4
23 Correct 0 ms 348 KB Correct answer: answer = 1
24 Correct 0 ms 348 KB Correct answer: answer = 5
25 Correct 1 ms 504 KB Correct answer: answer = 41
26 Correct 0 ms 348 KB Correct answer: answer = 71923
27 Correct 1 ms 348 KB Correct answer: answer = 77137
28 Correct 2 ms 348 KB Correct answer: answer = 764
29 Correct 2 ms 348 KB Correct answer: answer = 250000
30 Correct 2 ms 348 KB Correct answer: answer = 500
31 Correct 0 ms 348 KB Correct answer: answer = 32
32 Correct 2 ms 364 KB Correct answer: answer = 130050
33 Correct 2 ms 348 KB Correct answer: answer = 5110
34 Correct 1 ms 348 KB Correct answer: answer = 2626
35 Correct 1 ms 348 KB Correct answer: answer = 796
36 Correct 2 ms 348 KB Correct answer: answer = 7580
37 Correct 2 ms 348 KB Correct answer: answer = 1904
38 Correct 1 ms 348 KB Correct answer: answer = 996004
39 Correct 2 ms 348 KB Correct answer: answer = 38817
40 Correct 2 ms 348 KB Correct answer: answer = 4096
41 Correct 1 ms 348 KB Correct answer: answer = 1
42 Correct 1 ms 348 KB Correct answer: answer = 1
43 Correct 2 ms 348 KB Correct answer: answer = 2040
44 Correct 0 ms 348 KB Correct answer: answer = 2
45 Correct 0 ms 348 KB Correct answer: answer = 4
46 Correct 1 ms 348 KB Correct answer: answer = 9
47 Correct 0 ms 348 KB Correct answer: answer = 9
48 Correct 0 ms 348 KB Correct answer: answer = 21
49 Correct 0 ms 344 KB Correct answer: answer = 71
50 Correct 0 ms 348 KB Correct answer: answer = 77
51 Correct 1 ms 440 KB Correct answer: answer = 400
52 Correct 0 ms 348 KB Correct answer: answer = 996004
53 Correct 1 ms 344 KB Correct answer: answer = 997310
54 Correct 0 ms 348 KB Correct answer: answer = 990781
55 Correct 0 ms 348 KB Correct answer: answer = 996545
56 Correct 1 ms 348 KB Correct answer: answer = 484
57 Correct 1 ms 348 KB Correct answer: answer = 484
58 Correct 2 ms 348 KB Correct answer: answer = 63501
59 Correct 2 ms 348 KB Correct answer: answer = 323501
60 Correct 2 ms 348 KB Correct answer: answer = 752500
61 Correct 1 ms 448 KB Correct answer: answer = 761480
62 Correct 2 ms 348 KB Correct answer: answer = 758932
63 Correct 0 ms 348 KB Correct answer: answer = 1000000
64 Correct 2 ms 348 KB Correct answer: answer = 750500
65 Correct 0 ms 348 KB Correct answer: answer = 1000000
66 Correct 1 ms 344 KB Correct answer: answer = 250000
67 Correct 1 ms 348 KB Correct answer: answer = 250000
68 Correct 1 ms 348 KB Correct answer: answer = 1000000
69 Correct 0 ms 348 KB Correct answer: answer = 994009
70 Correct 1 ms 600 KB Correct answer: answer = 59315
71 Correct 2 ms 348 KB Correct answer: answer = 25454
72 Correct 2 ms 484 KB Correct answer: answer = 1504
73 Correct 1 ms 348 KB Correct answer: answer = 37486
74 Correct 1 ms 348 KB Correct answer: answer = 4284
75 Correct 1 ms 348 KB Correct answer: answer = 158008
76 Correct 1 ms 348 KB Correct answer: answer = 51860
77 Correct 1 ms 348 KB Correct answer: answer = 12985
78 Correct 1 ms 604 KB Correct answer: answer = 997864126212
79 Correct 1 ms 604 KB Correct answer: answer = 998608411647
80 Correct 1 ms 528 KB Correct answer: answer = 995265560477
81 Correct 12 ms 856 KB Correct answer: answer = 10125000
82 Correct 11 ms 604 KB Correct answer: answer = 2291668
83 Correct 6 ms 604 KB Correct answer: answer = 42388
84 Correct 7 ms 604 KB Correct answer: answer = 10318
85 Correct 6 ms 512 KB Correct answer: answer = 3416
86 Correct 17 ms 604 KB Correct answer: answer = 331708193881
87 Correct 18 ms 608 KB Correct answer: answer = 2861193756
88 Correct 16 ms 604 KB Correct answer: answer = 114646930
89 Correct 11 ms 600 KB Correct answer: answer = 9280921
90 Correct 11 ms 600 KB Correct answer: answer = 999984053400
91 Correct 14 ms 824 KB Correct answer: answer = 750935949134
92 Correct 1 ms 604 KB Correct answer: answer = 1000000000000
93 Correct 1 ms 604 KB Correct answer: answer = 998762383161
94 Correct 15 ms 604 KB Correct answer: answer = 23017412908
95 Correct 2 ms 604 KB Correct answer: answer = 728143410622
96 Correct 1 ms 604 KB Correct answer: answer = 2
97 Correct 11 ms 604 KB Correct answer: answer = 1824916
98 Correct 14 ms 604 KB Correct answer: answer = 10680029
99 Correct 13 ms 604 KB Correct answer: answer = 18351700
100 Correct 11 ms 840 KB Correct answer: answer = 16040026
101 Correct 3 ms 604 KB Correct answer: answer = 253968628325
102 Correct 6 ms 616 KB Correct answer: answer = 10267
103 Correct 13 ms 604 KB Correct answer: answer = 2582408
104 Correct 1 ms 528 KB Correct answer: answer = 78024964781
105 Correct 2 ms 604 KB Correct answer: answer = 9866346457
106 Correct 3 ms 704 KB Correct answer: answer = 3327720949
107 Correct 2 ms 604 KB Correct answer: answer = 86064128360
108 Correct 3 ms 604 KB Correct answer: answer = 12698259150
109 Correct 10 ms 604 KB Correct answer: answer = 1185259288
110 Correct 13 ms 3132 KB Correct answer: answer = 999889968863
111 Correct 13 ms 3032 KB Correct answer: answer = 999861384931
112 Correct 12 ms 3024 KB Correct answer: answer = 999811809929
113 Correct 12 ms 3028 KB Correct answer: answer = 999869756441
114 Correct 136 ms 5644 KB Correct answer: answer = 1700000000
115 Correct 141 ms 5188 KB Correct answer: answer = 131666670
116 Correct 44 ms 1884 KB Correct answer: answer = 89478486
117 Correct 46 ms 1860 KB Correct answer: answer = 4971040
118 Correct 44 ms 1884 KB Correct answer: answer = 2711494
119 Correct 137 ms 5196 KB Correct answer: answer = 25252530
120 Correct 148 ms 5392 KB Correct answer: answer = 62500000
121 Correct 203 ms 4176 KB Correct answer: answer = 333175097780
122 Correct 193 ms 4348 KB Correct answer: answer = 33121180179
123 Correct 180 ms 4180 KB Correct answer: answer = 9802314015
124 Correct 145 ms 5296 KB Correct answer: answer = 32567551
125 Correct 137 ms 5444 KB Correct answer: answer = 997525000000
126 Correct 165 ms 4240 KB Correct answer: answer = 752723538884
127 Correct 9 ms 2772 KB Correct answer: answer = 1000000000000
128 Correct 12 ms 3024 KB Correct answer: answer = 999978000121
129 Correct 14 ms 3028 KB Correct answer: answer = 745986144735
130 Correct 8 ms 2516 KB Correct answer: answer = 2
131 Correct 144 ms 5388 KB Correct answer: answer = 277966670
132 Correct 126 ms 5296 KB Correct answer: answer = 2500900082
133 Correct 31 ms 2768 KB Correct answer: answer = 301248349636
134 Correct 80 ms 2576 KB Correct answer: answer = 14118891
135 Correct 13 ms 3028 KB Correct answer: answer = 14384977265
136 Correct 14 ms 3024 KB Correct answer: answer = 3681368330
137 Correct 14 ms 3028 KB Correct answer: answer = 2720316816
138 Correct 25 ms 5320 KB Correct answer: answer = 999976000144
139 Correct 24 ms 5328 KB Correct answer: answer = 999856102410
140 Correct 30 ms 5316 KB Correct answer: answer = 999958401531
141 Correct 24 ms 5320 KB Correct answer: answer = 999769649944
142 Correct 24 ms 5316 KB Correct answer: answer = 999874525918
143 Correct 299 ms 10308 KB Correct answer: answer = 6050000000
144 Correct 293 ms 10556 KB Correct answer: answer = 1112500000
145 Correct 166 ms 6724 KB Correct answer: answer = 4294967296
146 Correct 185 ms 6632 KB Correct answer: answer = 87652406
147 Correct 185 ms 6732 KB Correct answer: answer = 6297664
148 Correct 180 ms 6732 KB Correct answer: answer = 196612
149 Correct 281 ms 10304 KB Correct answer: answer = 15015100
150 Correct 289 ms 10272 KB Correct answer: answer = 25000000
151 Correct 384 ms 8032 KB Correct answer: answer = 333230209550
152 Correct 342 ms 8004 KB Correct answer: answer = 917123769
153 Correct 318 ms 8036 KB Correct answer: answer = 95162
154 Correct 284 ms 10352 KB Correct answer: answer = 382616191
155 Correct 274 ms 10652 KB Correct answer: answer = 990033333400
156 Correct 276 ms 10440 KB Correct answer: answer = 990000100000
157 Correct 280 ms 7884 KB Correct answer: answer = 749998188180
158 Correct 20 ms 5324 KB Correct answer: answer = 1000000000000
159 Correct 31 ms 5296 KB Correct answer: answer = 999988000036
160 Correct 26 ms 5328 KB Correct answer: answer = 744929274393
161 Correct 15 ms 4556 KB Correct answer: answer = 2
162 Correct 275 ms 10304 KB Correct answer: answer = 1300024
163 Correct 282 ms 10284 KB Correct answer: answer = 5000700010
164 Correct 71 ms 5328 KB Correct answer: answer = 354997100800
165 Correct 158 ms 4680 KB Correct answer: answer = 257000
166 Correct 150 ms 5256 KB Correct answer: answer = 3765323
167 Correct 151 ms 5888 KB Correct answer: answer = 1525903
168 Correct 25 ms 5508 KB Correct answer: answer = 67618137730
169 Correct 26 ms 5504 KB Correct answer: answer = 12656680171
170 Correct 35 ms 5320 KB Correct answer: answer = 579831736
171 Correct 109 ms 6308 KB Correct answer: answer = 23605611
172 Correct 35 ms 5308 KB Correct answer: answer = 7052481200
173 Correct 54 ms 5464 KB Correct answer: answer = 1314039500
174 Correct 77 ms 5836 KB Correct answer: answer = 302484000
175 Correct 193 ms 7616 KB Correct answer: answer = 52348480