oj.uz

Submission #838959

# Submission time Handle Problem Language Result Execution time Memory
838959 2023-08-28T10:59:54 Z ballbattle Aliens (IOI16_aliens) C++14
100 / 100
 1488 ms 340872 KB 
#include "aliens.h"

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long ll;
typedef long double f;

typedef pair<ll,ll> pll;
typedef pair<f,ll> pfl;

typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<pfl> vp;
typedef vector<int> vi;

struct line {
    f c;
    f slope;
    pfl operator()(ll x) {return make_pair(c + ((f)x)*slope, my_k);}
    ll my_k;
};
typedef vector<line* > vl;

#define rep(a,b,c) for(ll a = b; a < c; a++)
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define all(a) a.begin(),a.end()
#define sz(a) a.size()

pfl operator+ (pfl a, pfl b) {return mp(a.first+b.first,a.second+b.second);}

pfl _dp(f lambda);
void insert(line*seg);
pfl query(f x);

ll n;
ll k;

vpll p;
vll h;

vp dp;

vl lines;

long long take_photos(int N, int M, int K, vi R, vi C) {
    k = K;
    p.clear();
    rep(i,0,N) {if (R[i] > C[i]) {swap(R[i],C[i]);}} // Flip over diagonal
    rep(i,0,N) {p.pb(mp(C[i],-R[i]));}
    sort(all(p)); // Sort in a way that makes worse points come before better points
    rep(i,0,N) {
        C[i] = p[i].first;
        R[i] = -p[i].second;
    }
    /*cout << "C[i] R[i]" << endl;
    rep(i,0,N) {cout << C[i] << " " << R[i] << endl;}*/
    // C[i] is in increasing order
    // R[i] is in decreasing order
    // The first point is the optimal

    p.clear();
    p.pb(mp(-1,-1)); // thing....
    rep(i,0,N) {

        while ((C[i] >= p[sz(p)-1].first) && (R[i] <= p[sz(p)-1].second)) { // Prune bad points
            p.pop_back();
        }
        p.pb(mp(C[i],R[i])); // Add points in (x,-y) format to p
    }
    
    /*cout << "points:" << endl;
    rep(i,0,sz(p)) {cout << p[i].first << " " << p[i].second << endl;}*/

    n = sz(p);
    h.resize(n,0);
    rep(i,0,n-1) {h[i] = p[i].first - p[i+1].second;}

    /*cout << "h:" << endl;
    rep(i,0,n) {cout << h[i] << " ";}
    cout << endl;*/

    /*rep(i,0,10) {cout << _dp(f(i)).first << endl;}*/

    ll ans = 1000000000001;

    f lo = f(0.0);
    f hi = f(1000000000001);
    f mid;
    pfl curr;
    rep(i,0,64) {
        mid = (lo)/f(2) + (hi)/f(2);
        //cout << mid << endl;
        curr = _dp(mid);
        //cout << (long double)(curr.first) << " " << curr.second << " " << (long double)(mid) << endl; 
        if (curr.second == min(k,n-1)) {
            ans = llround(curr.first - mid*curr.second);
            //cout << llround((long double)(curr.first - mid*curr.second)) << " " << (curr.first - mid*curr.second) << endl;
            break;
        } else if (curr.second > min(k,n-1)) {
            lo = mid;
        } else {
            hi = mid;
            /*ll tmp = round(curr.first - mid*(f(curr.second))); // Hotfix
            ans = min(tmp, ans);*/
        }
    }
    if (ans == 1000000000001) {ans = round(curr.first - mid*(f(k)));} // Based solution
    //if (ans==-1) {ans = round(curr.first - mid*(f(curr.second)));}

    //cout << n-1 << endl;
    return ans;
}

pfl _dp(f lambda) {
    lines.clear();
    dp.clear();
    dp.resize(n,mp((f)0,0));
    rep(i,0,n) {
        if (i!=0) dp[i] = mp((f)(p[i].first*p[i].first),0) + query((f)p[i].first) + mp(lambda,1); // wtf based

        line* new_line = new line;
        //lines.pb(new line);
        new_line->my_k = dp[i].second; // include k xd
        new_line->c = dp[i].first + (f)(p[i].first*p[i].first - 2*p[i].first*(h[i]+1) + ((h[i] < 0) ? (h[i]+1)*(h[i]+1) : 0));
        new_line->slope = (f)(-2*(p[i].first-h[i]-1));
        insert(new_line);
    }
    /*cout << "dp: ";
    rep(i,0,n) {cout << dp[i].first - lambda*dp[i].second << "," << dp[i].second << " ";}
    cout << endl;
    cout << lines.size() << ": ";
    rep(i,0,lines.size()) {cout << lines[i]->c << "," << lines[i]->slope << "," << lines[i]->my_k << " ";}
    cout << endl;*/
    return dp[n-1];
}

pfl query(f x) { // binary search
    ll lo = 0;
    ll hi = lines.size()-1;

    ll mid = (lo+hi)/2;
    while (lo != hi) {
        f intersect = (lines[mid]->c - lines[mid+1]->c)/(lines[mid+1]->slope - lines[mid]->slope);
        if (intersect < x) { // move right
            lo = mid+1;
        } else { // move left
            hi = mid;
        }
        mid = (lo+hi)/2;
    }
    return (*lines[mid])(x);
}

void insert(line*seg) { // done
    while (lines.size() >= 2) { // remove now defunct lines
        line* curr = lines.back();
        f i1 = (curr->c - seg->c)/(seg->slope - curr->slope);
        line* curr2 = lines[lines.size()-2];
        f i2 = (curr2->c - curr->c)/(curr->slope - curr2->slope);
        if (i1 < i2) {lines.pop_back();}
        else {break;}
    }
    lines.pb(seg);
}
// Insertsection of two lines
// y = x*slope + c
// x*s1 + c1 = x*s2 + c2
// x*(s1-s2) = c2-c1
// x = (c2-c1)/(s1-s2);

Subtask #1
4.0 / 4.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Correct answer: answer = 1
2 Correct 0 ms 212 KB Correct answer: answer = 4
3 Correct 1 ms 212 KB Correct answer: answer = 1
4 Correct 1 ms 232 KB Correct answer: answer = 5
5 Correct 1 ms 212 KB Correct answer: answer = 41
6 Correct 1 ms 340 KB Correct answer: answer = 71923
7 Correct 1 ms 628 KB Correct answer: answer = 77137
8 Correct 5 ms 1920 KB Correct answer: answer = 764
9 Correct 1 ms 340 KB Correct answer: answer = 250000
10 Correct 3 ms 1492 KB Correct answer: answer = 500
11 Correct 1 ms 212 KB Correct answer: answer = 32
12 Correct 2 ms 980 KB Correct answer: answer = 130050
13 Correct 6 ms 2260 KB Correct answer: answer = 5110
14 Correct 2 ms 852 KB Correct answer: answer = 2626
15 Correct 3 ms 1364 KB Correct answer: answer = 796
16 Correct 2 ms 1236 KB Correct answer: answer = 7580
17 Correct 6 ms 2348 KB Correct answer: answer = 1904
18 Correct 1 ms 340 KB Correct answer: answer = 996004
19 Correct 2 ms 1236 KB Correct answer: answer = 38817
20 Correct 4 ms 1236 KB Correct answer: answer = 4096
21 Correct 1 ms 212 KB Correct answer: answer = 1
22 Correct 1 ms 212 KB Correct answer: answer = 1
23 Correct 7 ms 2256 KB Correct answer: answer = 2040
24 Correct 1 ms 300 KB Correct answer: answer = 2

Subtask #3
9.0 / 9.0

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

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Correct answer: answer = 4
2 Correct 0 ms 212 KB Correct answer: answer = 4
3 Correct 1 ms 212 KB Correct answer: answer = 4
4 Correct 0 ms 212 KB Correct answer: answer = 12
5 Correct 1 ms 212 KB Correct answer: answer = 52
6 Correct 1 ms 212 KB Correct answer: answer = 210
7 Correct 1 ms 340 KB Correct answer: answer = 88
8 Correct 0 ms 304 KB Correct answer: answer = 7696
9 Correct 0 ms 212 KB Correct answer: answer = 1
10 Correct 1 ms 212 KB Correct answer: answer = 2374
11 Correct 1 ms 212 KB Correct answer: answer = 9502
12 Correct 0 ms 212 KB Correct answer: answer = 49
13 Correct 1 ms 340 KB Correct answer: answer = 151
14 Correct 1 ms 340 KB Correct answer: answer = 7550
15 Correct 1 ms 340 KB Correct answer: answer = 7220
16 Correct 1 ms 340 KB Correct answer: answer = 7550
17 Correct 1 ms 212 KB Correct answer: answer = 10000
18 Correct 0 ms 212 KB Correct answer: answer = 10000
19 Correct 1 ms 340 KB Correct answer: answer = 624
20 Correct 0 ms 212 KB Correct answer: answer = 10000
21 Correct 1 ms 212 KB Correct answer: answer = 1
22 Correct 0 ms 212 KB Correct answer: answer = 4
23 Correct 1 ms 212 KB Correct answer: answer = 1
24 Correct 1 ms 232 KB Correct answer: answer = 5
25 Correct 1 ms 212 KB Correct answer: answer = 41
26 Correct 1 ms 340 KB Correct answer: answer = 71923
27 Correct 1 ms 628 KB Correct answer: answer = 77137
28 Correct 5 ms 1920 KB Correct answer: answer = 764
29 Correct 1 ms 340 KB Correct answer: answer = 250000
30 Correct 3 ms 1492 KB Correct answer: answer = 500
31 Correct 1 ms 212 KB Correct answer: answer = 32
32 Correct 2 ms 980 KB Correct answer: answer = 130050
33 Correct 6 ms 2260 KB Correct answer: answer = 5110
34 Correct 2 ms 852 KB Correct answer: answer = 2626
35 Correct 3 ms 1364 KB Correct answer: answer = 796
36 Correct 2 ms 1236 KB Correct answer: answer = 7580
37 Correct 6 ms 2348 KB Correct answer: answer = 1904
38 Correct 1 ms 340 KB Correct answer: answer = 996004
39 Correct 2 ms 1236 KB Correct answer: answer = 38817
40 Correct 4 ms 1236 KB Correct answer: answer = 4096
41 Correct 1 ms 212 KB Correct answer: answer = 1
42 Correct 1 ms 212 KB Correct answer: answer = 1
43 Correct 7 ms 2256 KB Correct answer: answer = 2040
44 Correct 1 ms 300 KB Correct answer: answer = 2
45 Correct 1 ms 300 KB Correct answer: answer = 4
46 Correct 1 ms 212 KB Correct answer: answer = 9
47 Correct 0 ms 212 KB Correct answer: answer = 9
48 Correct 1 ms 212 KB Correct answer: answer = 21
49 Correct 1 ms 304 KB Correct answer: answer = 71
50 Correct 0 ms 212 KB Correct answer: answer = 77
51 Correct 0 ms 212 KB Correct answer: answer = 400
52 Correct 0 ms 300 KB Correct answer: answer = 996004
53 Correct 1 ms 212 KB Correct answer: answer = 997310
54 Correct 1 ms 212 KB Correct answer: answer = 990781
55 Correct 1 ms 300 KB Correct answer: answer = 996545
56 Correct 1 ms 212 KB Correct answer: answer = 484
57 Correct 1 ms 212 KB Correct answer: answer = 484
58 Correct 2 ms 1108 KB Correct answer: answer = 63501
59 Correct 3 ms 1320 KB Correct answer: answer = 323501
60 Correct 3 ms 1328 KB Correct answer: answer = 752500
61 Correct 1 ms 724 KB Correct answer: answer = 761480
62 Correct 3 ms 1216 KB Correct answer: answer = 758932
63 Correct 1 ms 212 KB Correct answer: answer = 1000000
64 Correct 4 ms 1492 KB Correct answer: answer = 750500
65 Correct 1 ms 212 KB Correct answer: answer = 1000000
66 Correct 1 ms 212 KB Correct answer: answer = 250000
67 Correct 1 ms 212 KB Correct answer: answer = 250000
68 Correct 1 ms 296 KB Correct answer: answer = 1000000
69 Correct 1 ms 300 KB Correct answer: answer = 994009
70 Correct 1 ms 596 KB Correct answer: answer = 59315
71 Correct 2 ms 980 KB Correct answer: answer = 25454
72 Correct 3 ms 1492 KB Correct answer: answer = 1504
73 Correct 1 ms 468 KB Correct answer: answer = 37486
74 Correct 3 ms 1320 KB Correct answer: answer = 4284
75 Correct 1 ms 340 KB Correct answer: answer = 158008
76 Correct 1 ms 468 KB Correct answer: answer = 51860
77 Correct 2 ms 556 KB Correct answer: answer = 12985
78 Correct 2 ms 468 KB Correct answer: answer = 997864126212
79 Correct 2 ms 436 KB Correct answer: answer = 998608411647
80 Correct 1 ms 468 KB Correct answer: answer = 995265560477
81 Correct 8 ms 4820 KB Correct answer: answer = 10125000
82 Correct 16 ms 6308 KB Correct answer: answer = 2291668
83 Correct 31 ms 8680 KB Correct answer: answer = 42388
84 Correct 25 ms 8560 KB Correct answer: answer = 10318
85 Correct 25 ms 8684 KB Correct answer: answer = 3416
86 Correct 3 ms 1280 KB Correct answer: answer = 331708193881
87 Correct 19 ms 6060 KB Correct answer: answer = 2861193756
88 Correct 26 ms 7832 KB Correct answer: answer = 114646930
89 Correct 22 ms 8588 KB Correct answer: answer = 9280921
90 Correct 55 ms 16744 KB Correct answer: answer = 999984053400
91 Correct 29 ms 8992 KB Correct answer: answer = 750935949134
92 Correct 1 ms 440 KB Correct answer: answer = 1000000000000
93 Correct 1 ms 468 KB Correct answer: answer = 998762383161
94 Correct 14 ms 4796 KB Correct answer: answer = 23017412908
95 Correct 2 ms 468 KB Correct answer: answer = 728143410622
96 Correct 1 ms 436 KB Correct answer: answer = 2
97 Correct 14 ms 6596 KB Correct answer: answer = 1824916
98 Correct 53 ms 16480 KB Correct answer: answer = 10680029
99 Correct 20 ms 7092 KB Correct answer: answer = 18351700
100 Correct 2 ms 824 KB Correct answer: answer = 16040026
101 Correct 2 ms 952 KB Correct answer: answer = 253968628325
102 Correct 26 ms 8396 KB Correct answer: answer = 10267
103 Correct 59 ms 16632 KB Correct answer: answer = 2582408
104 Correct 1 ms 468 KB Correct answer: answer = 78024964781
105 Correct 1 ms 508 KB Correct answer: answer = 9866346457
106 Correct 3 ms 1108 KB Correct answer: answer = 3327720949
107 Correct 3 ms 852 KB Correct answer: answer = 86064128360
108 Correct 5 ms 1748 KB Correct answer: answer = 12698259150
109 Correct 47 ms 13364 KB Correct answer: answer = 1185259288

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Correct answer: answer = 4
2 Correct 0 ms 212 KB Correct answer: answer = 4
3 Correct 1 ms 212 KB Correct answer: answer = 4
4 Correct 0 ms 212 KB Correct answer: answer = 12
5 Correct 1 ms 212 KB Correct answer: answer = 52
6 Correct 1 ms 212 KB Correct answer: answer = 210
7 Correct 1 ms 340 KB Correct answer: answer = 88
8 Correct 0 ms 304 KB Correct answer: answer = 7696
9 Correct 0 ms 212 KB Correct answer: answer = 1
10 Correct 1 ms 212 KB Correct answer: answer = 2374
11 Correct 1 ms 212 KB Correct answer: answer = 9502
12 Correct 0 ms 212 KB Correct answer: answer = 49
13 Correct 1 ms 340 KB Correct answer: answer = 151
14 Correct 1 ms 340 KB Correct answer: answer = 7550
15 Correct 1 ms 340 KB Correct answer: answer = 7220
16 Correct 1 ms 340 KB Correct answer: answer = 7550
17 Correct 1 ms 212 KB Correct answer: answer = 10000
18 Correct 0 ms 212 KB Correct answer: answer = 10000
19 Correct 1 ms 340 KB Correct answer: answer = 624
20 Correct 0 ms 212 KB Correct answer: answer = 10000
21 Correct 1 ms 212 KB Correct answer: answer = 1
22 Correct 0 ms 212 KB Correct answer: answer = 4
23 Correct 1 ms 212 KB Correct answer: answer = 1
24 Correct 1 ms 232 KB Correct answer: answer = 5
25 Correct 1 ms 212 KB Correct answer: answer = 41
26 Correct 1 ms 340 KB Correct answer: answer = 71923
27 Correct 1 ms 628 KB Correct answer: answer = 77137
28 Correct 5 ms 1920 KB Correct answer: answer = 764
29 Correct 1 ms 340 KB Correct answer: answer = 250000
30 Correct 3 ms 1492 KB Correct answer: answer = 500
31 Correct 1 ms 212 KB Correct answer: answer = 32
32 Correct 2 ms 980 KB Correct answer: answer = 130050
33 Correct 6 ms 2260 KB Correct answer: answer = 5110
34 Correct 2 ms 852 KB Correct answer: answer = 2626
35 Correct 3 ms 1364 KB Correct answer: answer = 796
36 Correct 2 ms 1236 KB Correct answer: answer = 7580
37 Correct 6 ms 2348 KB Correct answer: answer = 1904
38 Correct 1 ms 340 KB Correct answer: answer = 996004
39 Correct 2 ms 1236 KB Correct answer: answer = 38817
40 Correct 4 ms 1236 KB Correct answer: answer = 4096
41 Correct 1 ms 212 KB Correct answer: answer = 1
42 Correct 1 ms 212 KB Correct answer: answer = 1
43 Correct 7 ms 2256 KB Correct answer: answer = 2040
44 Correct 1 ms 300 KB Correct answer: answer = 2
45 Correct 1 ms 300 KB Correct answer: answer = 4
46 Correct 1 ms 212 KB Correct answer: answer = 9
47 Correct 0 ms 212 KB Correct answer: answer = 9
48 Correct 1 ms 212 KB Correct answer: answer = 21
49 Correct 1 ms 304 KB Correct answer: answer = 71
50 Correct 0 ms 212 KB Correct answer: answer = 77
51 Correct 0 ms 212 KB Correct answer: answer = 400
52 Correct 0 ms 300 KB Correct answer: answer = 996004
53 Correct 1 ms 212 KB Correct answer: answer = 997310
54 Correct 1 ms 212 KB Correct answer: answer = 990781
55 Correct 1 ms 300 KB Correct answer: answer = 996545
56 Correct 1 ms 212 KB Correct answer: answer = 484
57 Correct 1 ms 212 KB Correct answer: answer = 484
58 Correct 2 ms 1108 KB Correct answer: answer = 63501
59 Correct 3 ms 1320 KB Correct answer: answer = 323501
60 Correct 3 ms 1328 KB Correct answer: answer = 752500
61 Correct 1 ms 724 KB Correct answer: answer = 761480
62 Correct 3 ms 1216 KB Correct answer: answer = 758932
63 Correct 1 ms 212 KB Correct answer: answer = 1000000
64 Correct 4 ms 1492 KB Correct answer: answer = 750500
65 Correct 1 ms 212 KB Correct answer: answer = 1000000
66 Correct 1 ms 212 KB Correct answer: answer = 250000
67 Correct 1 ms 212 KB Correct answer: answer = 250000
68 Correct 1 ms 296 KB Correct answer: answer = 1000000
69 Correct 1 ms 300 KB Correct answer: answer = 994009
70 Correct 1 ms 596 KB Correct answer: answer = 59315
71 Correct 2 ms 980 KB Correct answer: answer = 25454
72 Correct 3 ms 1492 KB Correct answer: answer = 1504
73 Correct 1 ms 468 KB Correct answer: answer = 37486
74 Correct 3 ms 1320 KB Correct answer: answer = 4284
75 Correct 1 ms 340 KB Correct answer: answer = 158008
76 Correct 1 ms 468 KB Correct answer: answer = 51860
77 Correct 2 ms 556 KB Correct answer: answer = 12985
78 Correct 2 ms 468 KB Correct answer: answer = 997864126212
79 Correct 2 ms 436 KB Correct answer: answer = 998608411647
80 Correct 1 ms 468 KB Correct answer: answer = 995265560477
81 Correct 8 ms 4820 KB Correct answer: answer = 10125000
82 Correct 16 ms 6308 KB Correct answer: answer = 2291668
83 Correct 31 ms 8680 KB Correct answer: answer = 42388
84 Correct 25 ms 8560 KB Correct answer: answer = 10318
85 Correct 25 ms 8684 KB Correct answer: answer = 3416
86 Correct 3 ms 1280 KB Correct answer: answer = 331708193881
87 Correct 19 ms 6060 KB Correct answer: answer = 2861193756
88 Correct 26 ms 7832 KB Correct answer: answer = 114646930
89 Correct 22 ms 8588 KB Correct answer: answer = 9280921
90 Correct 55 ms 16744 KB Correct answer: answer = 999984053400
91 Correct 29 ms 8992 KB Correct answer: answer = 750935949134
92 Correct 1 ms 440 KB Correct answer: answer = 1000000000000
93 Correct 1 ms 468 KB Correct answer: answer = 998762383161
94 Correct 14 ms 4796 KB Correct answer: answer = 23017412908
95 Correct 2 ms 468 KB Correct answer: answer = 728143410622
96 Correct 1 ms 436 KB Correct answer: answer = 2
97 Correct 14 ms 6596 KB Correct answer: answer = 1824916
98 Correct 53 ms 16480 KB Correct answer: answer = 10680029
99 Correct 20 ms 7092 KB Correct answer: answer = 18351700
100 Correct 2 ms 824 KB Correct answer: answer = 16040026
101 Correct 2 ms 952 KB Correct answer: answer = 253968628325
102 Correct 26 ms 8396 KB Correct answer: answer = 10267
103 Correct 59 ms 16632 KB Correct answer: answer = 2582408
104 Correct 1 ms 468 KB Correct answer: answer = 78024964781
105 Correct 1 ms 508 KB Correct answer: answer = 9866346457
106 Correct 3 ms 1108 KB Correct answer: answer = 3327720949
107 Correct 3 ms 852 KB Correct answer: answer = 86064128360
108 Correct 5 ms 1748 KB Correct answer: answer = 12698259150
109 Correct 47 ms 13364 KB Correct answer: answer = 1185259288
110 Correct 14 ms 2856 KB Correct answer: answer = 999889968863
111 Correct 14 ms 2880 KB Correct answer: answer = 999861384931
112 Correct 15 ms 2892 KB Correct answer: answer = 999811809929
113 Correct 16 ms 2852 KB Correct answer: answer = 999869756441
114 Correct 66 ms 35776 KB Correct answer: answer = 1700000000
115 Correct 207 ms 67240 KB Correct answer: answer = 131666670
116 Correct 33 ms 17052 KB Correct answer: answer = 89478486
117 Correct 94 ms 30392 KB Correct answer: answer = 4971040
118 Correct 105 ms 33540 KB Correct answer: answer = 2711494
119 Correct 298 ms 86136 KB Correct answer: answer = 25252530
120 Correct 246 ms 76752 KB Correct answer: answer = 62500000
121 Correct 36 ms 13496 KB Correct answer: answer = 333175097780
122 Correct 140 ms 44120 KB Correct answer: answer = 33121180179
123 Correct 220 ms 65648 KB Correct answer: answer = 9802314015
124 Correct 264 ms 79800 KB Correct answer: answer = 32567551
125 Correct 327 ms 92392 KB Correct answer: answer = 997525000000
126 Correct 203 ms 66808 KB Correct answer: answer = 752723538884
127 Correct 11 ms 2764 KB Correct answer: answer = 1000000000000
128 Correct 13 ms 2892 KB Correct answer: answer = 999978000121
129 Correct 14 ms 2852 KB Correct answer: answer = 745986144735
130 Correct 8 ms 2380 KB Correct answer: answer = 2
131 Correct 132 ms 51548 KB Correct answer: answer = 277966670
132 Correct 18 ms 7496 KB Correct answer: answer = 2500900082
133 Correct 19 ms 6472 KB Correct answer: answer = 301248349636
134 Correct 150 ms 44652 KB Correct answer: answer = 14118891
135 Correct 15 ms 2892 KB Correct answer: answer = 14384977265
136 Correct 14 ms 3024 KB Correct answer: answer = 3681368330
137 Correct 16 ms 3528 KB Correct answer: answer = 2720316816

Subtask #6
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Correct answer: answer = 4
2 Correct 0 ms 212 KB Correct answer: answer = 4
3 Correct 1 ms 212 KB Correct answer: answer = 4
4 Correct 0 ms 212 KB Correct answer: answer = 12
5 Correct 1 ms 212 KB Correct answer: answer = 52
6 Correct 1 ms 212 KB Correct answer: answer = 210
7 Correct 1 ms 340 KB Correct answer: answer = 88
8 Correct 0 ms 304 KB Correct answer: answer = 7696
9 Correct 0 ms 212 KB Correct answer: answer = 1
10 Correct 1 ms 212 KB Correct answer: answer = 2374
11 Correct 1 ms 212 KB Correct answer: answer = 9502
12 Correct 0 ms 212 KB Correct answer: answer = 49
13 Correct 1 ms 340 KB Correct answer: answer = 151
14 Correct 1 ms 340 KB Correct answer: answer = 7550
15 Correct 1 ms 340 KB Correct answer: answer = 7220
16 Correct 1 ms 340 KB Correct answer: answer = 7550
17 Correct 1 ms 212 KB Correct answer: answer = 10000
18 Correct 0 ms 212 KB Correct answer: answer = 10000
19 Correct 1 ms 340 KB Correct answer: answer = 624
20 Correct 0 ms 212 KB Correct answer: answer = 10000
21 Correct 1 ms 212 KB Correct answer: answer = 1
22 Correct 0 ms 212 KB Correct answer: answer = 4
23 Correct 1 ms 212 KB Correct answer: answer = 1
24 Correct 1 ms 232 KB Correct answer: answer = 5
25 Correct 1 ms 212 KB Correct answer: answer = 41
26 Correct 1 ms 340 KB Correct answer: answer = 71923
27 Correct 1 ms 628 KB Correct answer: answer = 77137
28 Correct 5 ms 1920 KB Correct answer: answer = 764
29 Correct 1 ms 340 KB Correct answer: answer = 250000
30 Correct 3 ms 1492 KB Correct answer: answer = 500
31 Correct 1 ms 212 KB Correct answer: answer = 32
32 Correct 2 ms 980 KB Correct answer: answer = 130050
33 Correct 6 ms 2260 KB Correct answer: answer = 5110
34 Correct 2 ms 852 KB Correct answer: answer = 2626
35 Correct 3 ms 1364 KB Correct answer: answer = 796
36 Correct 2 ms 1236 KB Correct answer: answer = 7580
37 Correct 6 ms 2348 KB Correct answer: answer = 1904
38 Correct 1 ms 340 KB Correct answer: answer = 996004
39 Correct 2 ms 1236 KB Correct answer: answer = 38817
40 Correct 4 ms 1236 KB Correct answer: answer = 4096
41 Correct 1 ms 212 KB Correct answer: answer = 1
42 Correct 1 ms 212 KB Correct answer: answer = 1
43 Correct 7 ms 2256 KB Correct answer: answer = 2040
44 Correct 1 ms 300 KB Correct answer: answer = 2
45 Correct 1 ms 300 KB Correct answer: answer = 4
46 Correct 1 ms 212 KB Correct answer: answer = 9
47 Correct 0 ms 212 KB Correct answer: answer = 9
48 Correct 1 ms 212 KB Correct answer: answer = 21
49 Correct 1 ms 304 KB Correct answer: answer = 71
50 Correct 0 ms 212 KB Correct answer: answer = 77
51 Correct 0 ms 212 KB Correct answer: answer = 400
52 Correct 0 ms 300 KB Correct answer: answer = 996004
53 Correct 1 ms 212 KB Correct answer: answer = 997310
54 Correct 1 ms 212 KB Correct answer: answer = 990781
55 Correct 1 ms 300 KB Correct answer: answer = 996545
56 Correct 1 ms 212 KB Correct answer: answer = 484
57 Correct 1 ms 212 KB Correct answer: answer = 484
58 Correct 2 ms 1108 KB Correct answer: answer = 63501
59 Correct 3 ms 1320 KB Correct answer: answer = 323501
60 Correct 3 ms 1328 KB Correct answer: answer = 752500
61 Correct 1 ms 724 KB Correct answer: answer = 761480
62 Correct 3 ms 1216 KB Correct answer: answer = 758932
63 Correct 1 ms 212 KB Correct answer: answer = 1000000
64 Correct 4 ms 1492 KB Correct answer: answer = 750500
65 Correct 1 ms 212 KB Correct answer: answer = 1000000
66 Correct 1 ms 212 KB Correct answer: answer = 250000
67 Correct 1 ms 212 KB Correct answer: answer = 250000
68 Correct 1 ms 296 KB Correct answer: answer = 1000000
69 Correct 1 ms 300 KB Correct answer: answer = 994009
70 Correct 1 ms 596 KB Correct answer: answer = 59315
71 Correct 2 ms 980 KB Correct answer: answer = 25454
72 Correct 3 ms 1492 KB Correct answer: answer = 1504
73 Correct 1 ms 468 KB Correct answer: answer = 37486
74 Correct 3 ms 1320 KB Correct answer: answer = 4284
75 Correct 1 ms 340 KB Correct answer: answer = 158008
76 Correct 1 ms 468 KB Correct answer: answer = 51860
77 Correct 2 ms 556 KB Correct answer: answer = 12985
78 Correct 2 ms 468 KB Correct answer: answer = 997864126212
79 Correct 2 ms 436 KB Correct answer: answer = 998608411647
80 Correct 1 ms 468 KB Correct answer: answer = 995265560477
81 Correct 8 ms 4820 KB Correct answer: answer = 10125000
82 Correct 16 ms 6308 KB Correct answer: answer = 2291668
83 Correct 31 ms 8680 KB Correct answer: answer = 42388
84 Correct 25 ms 8560 KB Correct answer: answer = 10318
85 Correct 25 ms 8684 KB Correct answer: answer = 3416
86 Correct 3 ms 1280 KB Correct answer: answer = 331708193881
87 Correct 19 ms 6060 KB Correct answer: answer = 2861193756
88 Correct 26 ms 7832 KB Correct answer: answer = 114646930
89 Correct 22 ms 8588 KB Correct answer: answer = 9280921
90 Correct 55 ms 16744 KB Correct answer: answer = 999984053400
91 Correct 29 ms 8992 KB Correct answer: answer = 750935949134
92 Correct 1 ms 440 KB Correct answer: answer = 1000000000000
93 Correct 1 ms 468 KB Correct answer: answer = 998762383161
94 Correct 14 ms 4796 KB Correct answer: answer = 23017412908
95 Correct 2 ms 468 KB Correct answer: answer = 728143410622
96 Correct 1 ms 436 KB Correct answer: answer = 2
97 Correct 14 ms 6596 KB Correct answer: answer = 1824916
98 Correct 53 ms 16480 KB Correct answer: answer = 10680029
99 Correct 20 ms 7092 KB Correct answer: answer = 18351700
100 Correct 2 ms 824 KB Correct answer: answer = 16040026
101 Correct 2 ms 952 KB Correct answer: answer = 253968628325
102 Correct 26 ms 8396 KB Correct answer: answer = 10267
103 Correct 59 ms 16632 KB Correct answer: answer = 2582408
104 Correct 1 ms 468 KB Correct answer: answer = 78024964781
105 Correct 1 ms 508 KB Correct answer: answer = 9866346457
106 Correct 3 ms 1108 KB Correct answer: answer = 3327720949
107 Correct 3 ms 852 KB Correct answer: answer = 86064128360
108 Correct 5 ms 1748 KB Correct answer: answer = 12698259150
109 Correct 47 ms 13364 KB Correct answer: answer = 1185259288
110 Correct 14 ms 2856 KB Correct answer: answer = 999889968863
111 Correct 14 ms 2880 KB Correct answer: answer = 999861384931
112 Correct 15 ms 2892 KB Correct answer: answer = 999811809929
113 Correct 16 ms 2852 KB Correct answer: answer = 999869756441
114 Correct 66 ms 35776 KB Correct answer: answer = 1700000000
115 Correct 207 ms 67240 KB Correct answer: answer = 131666670
116 Correct 33 ms 17052 KB Correct answer: answer = 89478486
117 Correct 94 ms 30392 KB Correct answer: answer = 4971040
118 Correct 105 ms 33540 KB Correct answer: answer = 2711494
119 Correct 298 ms 86136 KB Correct answer: answer = 25252530
120 Correct 246 ms 76752 KB Correct answer: answer = 62500000
121 Correct 36 ms 13496 KB Correct answer: answer = 333175097780
122 Correct 140 ms 44120 KB Correct answer: answer = 33121180179
123 Correct 220 ms 65648 KB Correct answer: answer = 9802314015
124 Correct 264 ms 79800 KB Correct answer: answer = 32567551
125 Correct 327 ms 92392 KB Correct answer: answer = 997525000000
126 Correct 203 ms 66808 KB Correct answer: answer = 752723538884
127 Correct 11 ms 2764 KB Correct answer: answer = 1000000000000
128 Correct 13 ms 2892 KB Correct answer: answer = 999978000121
129 Correct 14 ms 2852 KB Correct answer: answer = 745986144735
130 Correct 8 ms 2380 KB Correct answer: answer = 2
131 Correct 132 ms 51548 KB Correct answer: answer = 277966670
132 Correct 18 ms 7496 KB Correct answer: answer = 2500900082
133 Correct 19 ms 6472 KB Correct answer: answer = 301248349636
134 Correct 150 ms 44652 KB Correct answer: answer = 14118891
135 Correct 15 ms 2892 KB Correct answer: answer = 14384977265
136 Correct 14 ms 3024 KB Correct answer: answer = 3681368330
137 Correct 16 ms 3528 KB Correct answer: answer = 2720316816
138 Correct 26 ms 5320 KB Correct answer: answer = 999976000144
139 Correct 26 ms 5284 KB Correct answer: answer = 999856102410
140 Correct 26 ms 5320 KB Correct answer: answer = 999958401531
141 Correct 32 ms 5276 KB Correct answer: answer = 999769649944
142 Correct 32 ms 5368 KB Correct answer: answer = 999874525918
143 Correct 122 ms 58920 KB Correct answer: answer = 6050000000
144 Correct 254 ms 90348 KB Correct answer: answer = 1112500000
145 Correct 19 ms 9768 KB Correct answer: answer = 4294967296
146 Correct 347 ms 100604 KB Correct answer: answer = 87652406
147 Correct 568 ms 145732 KB Correct answer: answer = 6297664
148 Correct 650 ms 162136 KB Correct answer: answer = 196612
149 Correct 859 ms 209600 KB Correct answer: answer = 15015100
150 Correct 784 ms 197040 KB Correct answer: answer = 25000000
151 Correct 72 ms 26384 KB Correct answer: answer = 333230209550
152 Correct 657 ms 175384 KB Correct answer: answer = 917123769
153 Correct 1012 ms 241748 KB Correct answer: answer = 95162
154 Correct 510 ms 140724 KB Correct answer: answer = 382616191
155 Correct 793 ms 197252 KB Correct answer: answer = 990033333400
156 Correct 1083 ms 253552 KB Correct answer: answer = 990000100000
157 Correct 1488 ms 340872 KB Correct answer: answer = 749998188180
158 Correct 19 ms 5320 KB Correct answer: answer = 1000000000000
159 Correct 26 ms 5416 KB Correct answer: answer = 999988000036
160 Correct 32 ms 5560 KB Correct answer: answer = 744929274393
161 Correct 16 ms 4424 KB Correct answer: answer = 2
162 Correct 1137 ms 253412 KB Correct answer: answer = 1300024
163 Correct 122 ms 58920 KB Correct answer: answer = 5000700010
164 Correct 36 ms 11276 KB Correct answer: answer = 354997100800
165 Correct 958 ms 205128 KB Correct answer: answer = 257000
166 Correct 1006 ms 205212 KB Correct answer: answer = 3765323
167 Correct 528 ms 123708 KB Correct answer: answer = 1525903
168 Correct 26 ms 5320 KB Correct answer: answer = 67618137730
169 Correct 26 ms 5376 KB Correct answer: answer = 12656680171
170 Correct 42 ms 10396 KB Correct answer: answer = 579831736
171 Correct 489 ms 117388 KB Correct answer: answer = 23605611
172 Correct 51 ms 12936 KB Correct answer: answer = 7052481200
173 Correct 114 ms 30480 KB Correct answer: answer = 1314039500
174 Correct 208 ms 52112 KB Correct answer: answer = 302484000
175 Correct 1094 ms 247680 KB Correct answer: answer = 52348480