oj.uz

Submission #108523

# Submission time Handle Problem Language Result Execution time Memory
108523 2019-04-30T06:39:37 Z rajarshi_basu Aliens (IOI16_aliens) C++14
60 / 100
 1151 ms 255296 KB 
#include <iostream>
#include <vector>
#include <set>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <stdio.h>
#include <cmath>
#include <queue>
//#include <string>
//#include <map>
//#include <complex>
//#include <chrono>
//#include <random>
//#include <stack>
//#include <set>
//#include <fstream>
 
#define FOR(i,n) for(int i = 0;i < n; i++)
#define FORE(i,a,b) for(int i = a; i <= b ; i++)
#define ss second
#define ff first
#define ll long long int
#define ii pair<ll,ll>
#define il pair<int,ll>
#define li pair<ll,int>
#define x ff
#define y ss
#define lii pair<ll,pair<int,int> > 
#define piil pair<int ,pair<int,int> > 
#define iii pair<pair<int,int>,int> 
#define pll pair<ll,ll>
#define vi vector<int>
#define pb push_back
#define mp make_pair
 
#include "aliens.h"
 
using namespace std;
 
const ll INF = 1e18;
 
vector<ii> all;
 
vector<ii> reduceList(vector<ii> v){
    sort(v.begin(), v.end());
    vector<ii> res;
    ll mx = 0;
    for(auto e:v){
 
        if(res.empty())res.pb(e);
        else if(res.back().ff < e.ff){
            if(e.ss > mx)res.pb(e);
        }else{
            res.back() = e;
        }
        mx = max(mx,e.ss);
    }
    return res;
}
 
vector<ii> createRanges(vi r,vi c,int n){
    vector<ii> all;
    FOR(i,n)all.pb({min(r[i],c[i]),max(r[i],c[i])});
    return all;
}
 
ll C1[50*1000+1];
void prec(){
    C1[0] = 0;  
    FORE(i,1,(int)all.size()-1){
        C1[i] = max((ll)0,all[i-1].ss - all[i].ff+1);
        C1[i] *= C1[i];
    }
}
 
ll cost(int t,int i){
    i--;
    //cout << "afsf " << i << " " << all.size() <<  endl;
    ll t1 = all[i].ss - all[t].ff + 1; t1*=t1;
    ll t2 = C1[t];
    //cout << t1 << " " << t2 << endl;
    //cout << t1-t2 << endl;
    return t1 - t2;
}
 
struct Node{
        int left;
        int right;
        pll p;
        Node(){
            left = -1;
            right = -1;
            p = {1e9,1e9};
        }
        void init(){
            left = -1;
            right = -1;
            p = {1e9,1e9};
        }
    };
 
 
Node B[500*100*100];
int PTR = 0;
inline int get(){
    //cout << PTR << endl;
    B[PTR].init();
    //cout << "wow" << endl;
    return PTR++;
}
 
 
class Segtree{    
    int n;
 
    
    int head;
    inline void expand(int& nd){
        
        //cout << nd << endl;
    }
 
    inline ll eval(pll p,ll x){
        return p.ff*x+ p.ss;
    }
 
    inline double intersect(pll p1,pll p2){
        return (p1.ss-p2.ss)*1.0/(p2.ff-p1.ff);
    }
 
    void update(int& node,int ss,int se,pll ln){
        if(node == -1)node = get();
        if(ss == se){
            if(eval(ln,ss) < eval(B[node].p,ss)){
                B[node].p = ln;
            }
            return;
        }
        ll v1 = eval(ln,ss);
        ll v2 = eval(ln,se);
        ll v3 = eval(B[node].p,ss);
        ll v4 = eval(B[node].p,se);
        if(v1 <= v3 and v2 <= v4){
            B[node].p = ln;
            return;
        }else if(v3 <= v1 and v4 <= v2){
            return;
        }
        int mid = (ss+se)/2;
        update(B[node].left,ss,mid,ln);
        update(B[node].right,mid+1,se,ln);
    }
    ll query(int node,int ss,int se,int i){
        if(node == -1) return INF;
        if(i > se or i < ss)return INF;
        if(ss == se){
            return eval(B[node].p,i);
        }
        int mid = (ss+se)/2;
        return min(min(eval(B[node].p,i),query(B[node].left,ss,mid,i)),query(B[node].right,mid+1,se,i));
    }
 
    public : 
    Segtree(){
        PTR = 0;
        head = get();
      //  cout << head << endl;
    }
    inline void init(){
        PTR = 0;
        head = get();
    }
 
    inline void addLine(ll m,ll c){
        update(head,0,1e6+1,{m,c});
    }
 
    inline ll query(ll x){
        return query(head,0,1e6+1,x);
    }
};
 
class SqrtSegtree{
    deque<pll> cht;
    deque<pll> buffer;
    vector<pll> all;
 
    #define ld long double
    inline ld intersect(pll p1,pll p2){
        return ((ld)(p1.ss-p2.ss)*1.0)/(p2.ff-p1.ff);
    }
 
    inline ll eval(pll p1,ll x){
        return p1.ff*x+p1.ss;
    }
 
 
    inline void update(){
        if(buffer.size() > 1){
            //reverse(cht.begin(), cht.end());
            //for(auto e:cht)buffer.push_front(e);
            //cht.clear();
 
            for(auto e:buffer){
                while(cht.size() > 1 and intersect(cht[(int)cht.size()-2],e) > intersect(cht.back(),e))
                    cht.pop_back();
 
                cht.push_back(e);
            }
            buffer.clear();
        }
 
    }
 
    ll binsrch(ll x){
        int lo = 0;int hi = (int)cht.size()-1;
        ll best = INF;
        while(hi >= lo){
            if(hi-lo < 5){
                FORE(i,lo,hi)
                    best = min(best,eval(cht[i],x));
                break;
            }
            int mid = (lo+hi)/2;
            ll val1 = eval(cht[mid],x);
            ll val2 = eval(cht[mid+1],x);
            ll val3 = eval(cht[mid-1],x);
            best = min(best,min(val1,min(val2,val3)));
            if(val1 < val2 and val1 < val3){
                break;
            }else if(val1 >= val2){
                lo = mid+1;
            }else if(val1 >= val3){
                hi = mid-1;
            }
        }
        return best;
    }
 
    public : 
    inline void addLine(ll m,ll c){
        buffer.pb({m,c});
        all.pb({m,c});
        update();
    }
 
    inline ll query(ll x){ 
        ll best = binsrch(x);
        for(auto e:buffer)
        {
            best = min(best, eval(e,x));
        }
        return best;
    }
    inline void init(){
        buffer.clear();
        cht.clear();
    }
};
 
ll dp[2][50*1000+1];
int opt[2][50*1000+1];
ll E[50*1000+1];
//int opt[50*1000+1][2];
//Segtree ds[50*1000+1];
void computeDp(int k){
   // cout << "e" << endl;
    int n = all.size();
    k = min(n,k);
    FOR(i,n+1)dp[0][i] = INF;
    dp[0][0] = 0;
   // cout << "j" << endl;
    vector<pll> lns;
    vector<ll> add;
    //cout << "d" << endl;
    FOR(i,n){
        add.pb(all[i].ss*all[i].ss + 1 + 2*all[i].ss);
    }
    
    FOR(i,n)E[i] = all[i].ff*all[i].ff - 2*all[i].ff;
    //cout << "e" << endl;
    SqrtSegtree ds;
    FOR(j,k+1){
        if(j == 0)continue;
        dp[1][0] = 0;
        //cout << " e" << endl;
        ds.init();
        //cout << "d" << endl;
        
        for(int i = 1;i <= n;i++){
            ds.addLine((-2*all[i-1].ff),(dp[0][i-1] - C1[i-1] + E[i-1]));
            ll mn = ds.query(all[i-1].ss);
            dp[1][i] = mn + add[i-1];
            
        }
        FOR(i,n)dp[0][i] = dp[1][i];
    }
}
 
 
void computeDp2(int k){
    int n = all.size();
    k = min(n,k);
    FOR(i,n+1)dp[0][i] = INF;
    dp[0][0] = 0;
    FOR(j,k+1){
        if(j == 0)continue;
        dp[1][0] = 0;
        for(int i = n;i>=1;i--){
            ll opti = dp[0][0]+cost(0,i);
            int ind = 1;
 
            FORE(t,max(opt[0][i],2),(i==n?n:opt[1][i+1])){
                if(opti > dp[0][t-1] + cost(t-1,i)){
                    opti = dp[0][t-1] + cost(t-1,i);
                    ind = t;
                }
            }
            opt[1][i] = ind;
            dp[1][i] = opti;
        }
        FOR(i,n)dp[0][i] = dp[1][i],opt[0][i]= opt[1][i];
    }
}
 
ll take_photos(int n,int m,int k,vi r,vi c){
    all = reduceList(createRanges(r,c,n));
    prec();
    if(k > 101)computeDp2(k);else
    //for(auto e:all)cout << e.ff<< ";"<<e.ss << endl;
    computeDp(k);/*
    FOR(i,min((int)all.size(),k)+1){
    FOR(j,all.size()+1){
        cout << dp[i][j] << " ";
    };cout << endl;}*/
    return dp[1][all.size()];
    //return 0;
}
 
 
/*
int main(){
    //int a[2] = {2,4,4,4,4};
    //int b[2] = {3,5,6,5,6};
    vi a;
    vi b;
    a.pb(1);a.pb(4);
    b.pb(6);b.pb(7);
    cout << take_photos(2,7,2,a,b) << endl;
    return 0;
}
 
*/

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 117792 KB Correct answer: answer = 4
2 Correct 85 ms 117724 KB Correct answer: answer = 4
3 Correct 106 ms 117684 KB Correct answer: answer = 4
4 Correct 94 ms 117768 KB Correct answer: answer = 12
5 Correct 91 ms 117756 KB Correct answer: answer = 52
6 Correct 83 ms 117752 KB Correct answer: answer = 210
7 Correct 96 ms 117752 KB Correct answer: answer = 88
8 Correct 96 ms 117688 KB Correct answer: answer = 7696
9 Correct 101 ms 117688 KB Correct answer: answer = 1
10 Correct 107 ms 117684 KB Correct answer: answer = 2374
11 Correct 92 ms 117692 KB Correct answer: answer = 9502
12 Correct 115 ms 117732 KB Correct answer: answer = 49
13 Correct 92 ms 117792 KB Correct answer: answer = 151
14 Correct 97 ms 117788 KB Correct answer: answer = 7550
15 Correct 100 ms 117832 KB Correct answer: answer = 7220
16 Correct 89 ms 117848 KB Correct answer: answer = 7550
17 Correct 89 ms 117736 KB Correct answer: answer = 10000
18 Correct 100 ms 117752 KB Correct answer: answer = 10000
19 Correct 94 ms 117736 KB Correct answer: answer = 624
20 Correct 95 ms 117776 KB Correct answer: answer = 10000

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 117800 KB Correct answer: answer = 1
2 Correct 103 ms 117744 KB Correct answer: answer = 4
3 Correct 97 ms 117708 KB Correct answer: answer = 1
4 Correct 103 ms 117748 KB Correct answer: answer = 5
5 Correct 86 ms 117788 KB Correct answer: answer = 41
6 Correct 96 ms 117684 KB Correct answer: answer = 71923
7 Correct 95 ms 117872 KB Correct answer: answer = 77137
8 Correct 101 ms 117852 KB Correct answer: answer = 764
9 Correct 108 ms 117772 KB Correct answer: answer = 250000
10 Correct 107 ms 117852 KB Correct answer: answer = 500
11 Correct 121 ms 117804 KB Correct answer: answer = 32
12 Correct 94 ms 117836 KB Correct answer: answer = 130050
13 Correct 99 ms 118432 KB Correct answer: answer = 5110
14 Correct 97 ms 117980 KB Correct answer: answer = 2626
15 Correct 101 ms 118452 KB Correct answer: answer = 796
16 Correct 107 ms 118404 KB Correct answer: answer = 7580
17 Correct 109 ms 117840 KB Correct answer: answer = 1904
18 Correct 99 ms 117788 KB Correct answer: answer = 996004
19 Correct 98 ms 118072 KB Correct answer: answer = 38817
20 Correct 94 ms 118948 KB Correct answer: answer = 4096
21 Correct 120 ms 117748 KB Correct answer: answer = 1
22 Correct 85 ms 117752 KB Correct answer: answer = 1
23 Correct 90 ms 117824 KB Correct answer: answer = 2040
24 Correct 87 ms 117712 KB Correct answer: answer = 2

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 117792 KB Correct answer: answer = 4
2 Correct 85 ms 117724 KB Correct answer: answer = 4
3 Correct 106 ms 117684 KB Correct answer: answer = 4
4 Correct 94 ms 117768 KB Correct answer: answer = 12
5 Correct 91 ms 117756 KB Correct answer: answer = 52
6 Correct 83 ms 117752 KB Correct answer: answer = 210
7 Correct 96 ms 117752 KB Correct answer: answer = 88
8 Correct 96 ms 117688 KB Correct answer: answer = 7696
9 Correct 101 ms 117688 KB Correct answer: answer = 1
10 Correct 107 ms 117684 KB Correct answer: answer = 2374
11 Correct 92 ms 117692 KB Correct answer: answer = 9502
12 Correct 115 ms 117732 KB Correct answer: answer = 49
13 Correct 92 ms 117792 KB Correct answer: answer = 151
14 Correct 97 ms 117788 KB Correct answer: answer = 7550
15 Correct 100 ms 117832 KB Correct answer: answer = 7220
16 Correct 89 ms 117848 KB Correct answer: answer = 7550
17 Correct 89 ms 117736 KB Correct answer: answer = 10000
18 Correct 100 ms 117752 KB Correct answer: answer = 10000
19 Correct 94 ms 117736 KB Correct answer: answer = 624
20 Correct 95 ms 117776 KB Correct answer: answer = 10000
21 Correct 114 ms 117800 KB Correct answer: answer = 1
22 Correct 103 ms 117744 KB Correct answer: answer = 4
23 Correct 97 ms 117708 KB Correct answer: answer = 1
24 Correct 103 ms 117748 KB Correct answer: answer = 5
25 Correct 86 ms 117788 KB Correct answer: answer = 41
26 Correct 96 ms 117684 KB Correct answer: answer = 71923
27 Correct 95 ms 117872 KB Correct answer: answer = 77137
28 Correct 101 ms 117852 KB Correct answer: answer = 764
29 Correct 108 ms 117772 KB Correct answer: answer = 250000
30 Correct 107 ms 117852 KB Correct answer: answer = 500
31 Correct 121 ms 117804 KB Correct answer: answer = 32
32 Correct 94 ms 117836 KB Correct answer: answer = 130050
33 Correct 99 ms 118432 KB Correct answer: answer = 5110
34 Correct 97 ms 117980 KB Correct answer: answer = 2626
35 Correct 101 ms 118452 KB Correct answer: answer = 796
36 Correct 107 ms 118404 KB Correct answer: answer = 7580
37 Correct 109 ms 117840 KB Correct answer: answer = 1904
38 Correct 99 ms 117788 KB Correct answer: answer = 996004
39 Correct 98 ms 118072 KB Correct answer: answer = 38817
40 Correct 94 ms 118948 KB Correct answer: answer = 4096
41 Correct 120 ms 117748 KB Correct answer: answer = 1
42 Correct 85 ms 117752 KB Correct answer: answer = 1
43 Correct 90 ms 117824 KB Correct answer: answer = 2040
44 Correct 87 ms 117712 KB Correct answer: answer = 2
45 Correct 92 ms 117728 KB Correct answer: answer = 4
46 Correct 107 ms 117808 KB Correct answer: answer = 9
47 Correct 110 ms 117744 KB Correct answer: answer = 9
48 Correct 90 ms 117800 KB Correct answer: answer = 21
49 Correct 114 ms 117796 KB Correct answer: answer = 71
50 Correct 107 ms 117704 KB Correct answer: answer = 77
51 Correct 102 ms 117772 KB Correct answer: answer = 400
52 Correct 96 ms 117816 KB Correct answer: answer = 996004
53 Correct 101 ms 117748 KB Correct answer: answer = 997310
54 Correct 111 ms 117816 KB Correct answer: answer = 990781
55 Correct 92 ms 117764 KB Correct answer: answer = 996545
56 Correct 95 ms 117732 KB Correct answer: answer = 484
57 Correct 93 ms 117724 KB Correct answer: answer = 484
58 Correct 110 ms 117860 KB Correct answer: answer = 63501
59 Correct 101 ms 118140 KB Correct answer: answer = 323501
60 Correct 101 ms 118960 KB Correct answer: answer = 752500
61 Correct 109 ms 117980 KB Correct answer: answer = 761480
62 Correct 116 ms 117824 KB Correct answer: answer = 758932
63 Correct 95 ms 117784 KB Correct answer: answer = 1000000
64 Correct 102 ms 117852 KB Correct answer: answer = 750500
65 Correct 93 ms 117792 KB Correct answer: answer = 1000000
66 Correct 108 ms 117808 KB Correct answer: answer = 250000
67 Correct 102 ms 117780 KB Correct answer: answer = 250000
68 Correct 108 ms 117752 KB Correct answer: answer = 1000000
69 Correct 114 ms 117732 KB Correct answer: answer = 994009
70 Correct 112 ms 117916 KB Correct answer: answer = 59315
71 Correct 100 ms 118404 KB Correct answer: answer = 25454
72 Correct 104 ms 117720 KB Correct answer: answer = 1504
73 Correct 124 ms 117912 KB Correct answer: answer = 37486
74 Correct 122 ms 117768 KB Correct answer: answer = 4284
75 Correct 103 ms 117744 KB Correct answer: answer = 158008
76 Correct 107 ms 117748 KB Correct answer: answer = 51860
77 Correct 92 ms 117852 KB Correct answer: answer = 12985

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 117792 KB Correct answer: answer = 4
2 Correct 85 ms 117724 KB Correct answer: answer = 4
3 Correct 106 ms 117684 KB Correct answer: answer = 4
4 Correct 94 ms 117768 KB Correct answer: answer = 12
5 Correct 91 ms 117756 KB Correct answer: answer = 52
6 Correct 83 ms 117752 KB Correct answer: answer = 210
7 Correct 96 ms 117752 KB Correct answer: answer = 88
8 Correct 96 ms 117688 KB Correct answer: answer = 7696
9 Correct 101 ms 117688 KB Correct answer: answer = 1
10 Correct 107 ms 117684 KB Correct answer: answer = 2374
11 Correct 92 ms 117692 KB Correct answer: answer = 9502
12 Correct 115 ms 117732 KB Correct answer: answer = 49
13 Correct 92 ms 117792 KB Correct answer: answer = 151
14 Correct 97 ms 117788 KB Correct answer: answer = 7550
15 Correct 100 ms 117832 KB Correct answer: answer = 7220
16 Correct 89 ms 117848 KB Correct answer: answer = 7550
17 Correct 89 ms 117736 KB Correct answer: answer = 10000
18 Correct 100 ms 117752 KB Correct answer: answer = 10000
19 Correct 94 ms 117736 KB Correct answer: answer = 624
20 Correct 95 ms 117776 KB Correct answer: answer = 10000
21 Correct 114 ms 117800 KB Correct answer: answer = 1
22 Correct 103 ms 117744 KB Correct answer: answer = 4
23 Correct 97 ms 117708 KB Correct answer: answer = 1
24 Correct 103 ms 117748 KB Correct answer: answer = 5
25 Correct 86 ms 117788 KB Correct answer: answer = 41
26 Correct 96 ms 117684 KB Correct answer: answer = 71923
27 Correct 95 ms 117872 KB Correct answer: answer = 77137
28 Correct 101 ms 117852 KB Correct answer: answer = 764
29 Correct 108 ms 117772 KB Correct answer: answer = 250000
30 Correct 107 ms 117852 KB Correct answer: answer = 500
31 Correct 121 ms 117804 KB Correct answer: answer = 32
32 Correct 94 ms 117836 KB Correct answer: answer = 130050
33 Correct 99 ms 118432 KB Correct answer: answer = 5110
34 Correct 97 ms 117980 KB Correct answer: answer = 2626
35 Correct 101 ms 118452 KB Correct answer: answer = 796
36 Correct 107 ms 118404 KB Correct answer: answer = 7580
37 Correct 109 ms 117840 KB Correct answer: answer = 1904
38 Correct 99 ms 117788 KB Correct answer: answer = 996004
39 Correct 98 ms 118072 KB Correct answer: answer = 38817
40 Correct 94 ms 118948 KB Correct answer: answer = 4096
41 Correct 120 ms 117748 KB Correct answer: answer = 1
42 Correct 85 ms 117752 KB Correct answer: answer = 1
43 Correct 90 ms 117824 KB Correct answer: answer = 2040
44 Correct 87 ms 117712 KB Correct answer: answer = 2
45 Correct 92 ms 117728 KB Correct answer: answer = 4
46 Correct 107 ms 117808 KB Correct answer: answer = 9
47 Correct 110 ms 117744 KB Correct answer: answer = 9
48 Correct 90 ms 117800 KB Correct answer: answer = 21
49 Correct 114 ms 117796 KB Correct answer: answer = 71
50 Correct 107 ms 117704 KB Correct answer: answer = 77
51 Correct 102 ms 117772 KB Correct answer: answer = 400
52 Correct 96 ms 117816 KB Correct answer: answer = 996004
53 Correct 101 ms 117748 KB Correct answer: answer = 997310
54 Correct 111 ms 117816 KB Correct answer: answer = 990781
55 Correct 92 ms 117764 KB Correct answer: answer = 996545
56 Correct 95 ms 117732 KB Correct answer: answer = 484
57 Correct 93 ms 117724 KB Correct answer: answer = 484
58 Correct 110 ms 117860 KB Correct answer: answer = 63501
59 Correct 101 ms 118140 KB Correct answer: answer = 323501
60 Correct 101 ms 118960 KB Correct answer: answer = 752500
61 Correct 109 ms 117980 KB Correct answer: answer = 761480
62 Correct 116 ms 117824 KB Correct answer: answer = 758932
63 Correct 95 ms 117784 KB Correct answer: answer = 1000000
64 Correct 102 ms 117852 KB Correct answer: answer = 750500
65 Correct 93 ms 117792 KB Correct answer: answer = 1000000
66 Correct 108 ms 117808 KB Correct answer: answer = 250000
67 Correct 102 ms 117780 KB Correct answer: answer = 250000
68 Correct 108 ms 117752 KB Correct answer: answer = 1000000
69 Correct 114 ms 117732 KB Correct answer: answer = 994009
70 Correct 112 ms 117916 KB Correct answer: answer = 59315
71 Correct 100 ms 118404 KB Correct answer: answer = 25454
72 Correct 104 ms 117720 KB Correct answer: answer = 1504
73 Correct 124 ms 117912 KB Correct answer: answer = 37486
74 Correct 122 ms 117768 KB Correct answer: answer = 4284
75 Correct 103 ms 117744 KB Correct answer: answer = 158008
76 Correct 107 ms 117748 KB Correct answer: answer = 51860
77 Correct 92 ms 117852 KB Correct answer: answer = 12985
78 Correct 102 ms 117932 KB Correct answer: answer = 997864126212
79 Correct 91 ms 117940 KB Correct answer: answer = 998608411647
80 Correct 112 ms 117936 KB Correct answer: answer = 995265560477
81 Correct 103 ms 118364 KB Correct answer: answer = 10125000
82 Correct 92 ms 118708 KB Correct answer: answer = 2291668
83 Correct 110 ms 122224 KB Correct answer: answer = 42388
84 Correct 104 ms 118008 KB Correct answer: answer = 10318
85 Correct 152 ms 118016 KB Correct answer: answer = 3416
86 Correct 96 ms 118500 KB Correct answer: answer = 331708193881
87 Correct 150 ms 118188 KB Correct answer: answer = 2861193756
88 Correct 198 ms 118248 KB Correct answer: answer = 114646930
89 Correct 154 ms 122344 KB Correct answer: answer = 9280921
90 Correct 133 ms 118224 KB Correct answer: answer = 999984053400
91 Correct 199 ms 118204 KB Correct answer: answer = 750935949134
92 Correct 110 ms 118008 KB Correct answer: answer = 1000000000000
93 Correct 94 ms 117960 KB Correct answer: answer = 998762383161
94 Correct 126 ms 122392 KB Correct answer: answer = 23017412908
95 Correct 102 ms 118048 KB Correct answer: answer = 728143410622
96 Correct 115 ms 117908 KB Correct answer: answer = 2
97 Correct 107 ms 119252 KB Correct answer: answer = 1824916
98 Correct 166 ms 118116 KB Correct answer: answer = 10680029
99 Correct 140 ms 118240 KB Correct answer: answer = 18351700
100 Correct 103 ms 118392 KB Correct answer: answer = 16040026
101 Correct 102 ms 117980 KB Correct answer: answer = 253968628325
102 Correct 156 ms 118008 KB Correct answer: answer = 10267
103 Correct 216 ms 118264 KB Correct answer: answer = 2582408
104 Correct 100 ms 118008 KB Correct answer: answer = 78024964781
105 Correct 117 ms 117980 KB Correct answer: answer = 9866346457
106 Correct 108 ms 119108 KB Correct answer: answer = 3327720949
107 Correct 108 ms 117988 KB Correct answer: answer = 86064128360
108 Correct 102 ms 118052 KB Correct answer: answer = 12698259150
109 Correct 204 ms 118148 KB Correct answer: answer = 1185259288

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 117792 KB Correct answer: answer = 4
2 Correct 85 ms 117724 KB Correct answer: answer = 4
3 Correct 106 ms 117684 KB Correct answer: answer = 4
4 Correct 94 ms 117768 KB Correct answer: answer = 12
5 Correct 91 ms 117756 KB Correct answer: answer = 52
6 Correct 83 ms 117752 KB Correct answer: answer = 210
7 Correct 96 ms 117752 KB Correct answer: answer = 88
8 Correct 96 ms 117688 KB Correct answer: answer = 7696
9 Correct 101 ms 117688 KB Correct answer: answer = 1
10 Correct 107 ms 117684 KB Correct answer: answer = 2374
11 Correct 92 ms 117692 KB Correct answer: answer = 9502
12 Correct 115 ms 117732 KB Correct answer: answer = 49
13 Correct 92 ms 117792 KB Correct answer: answer = 151
14 Correct 97 ms 117788 KB Correct answer: answer = 7550
15 Correct 100 ms 117832 KB Correct answer: answer = 7220
16 Correct 89 ms 117848 KB Correct answer: answer = 7550
17 Correct 89 ms 117736 KB Correct answer: answer = 10000
18 Correct 100 ms 117752 KB Correct answer: answer = 10000
19 Correct 94 ms 117736 KB Correct answer: answer = 624
20 Correct 95 ms 117776 KB Correct answer: answer = 10000
21 Correct 114 ms 117800 KB Correct answer: answer = 1
22 Correct 103 ms 117744 KB Correct answer: answer = 4
23 Correct 97 ms 117708 KB Correct answer: answer = 1
24 Correct 103 ms 117748 KB Correct answer: answer = 5
25 Correct 86 ms 117788 KB Correct answer: answer = 41
26 Correct 96 ms 117684 KB Correct answer: answer = 71923
27 Correct 95 ms 117872 KB Correct answer: answer = 77137
28 Correct 101 ms 117852 KB Correct answer: answer = 764
29 Correct 108 ms 117772 KB Correct answer: answer = 250000
30 Correct 107 ms 117852 KB Correct answer: answer = 500
31 Correct 121 ms 117804 KB Correct answer: answer = 32
32 Correct 94 ms 117836 KB Correct answer: answer = 130050
33 Correct 99 ms 118432 KB Correct answer: answer = 5110
34 Correct 97 ms 117980 KB Correct answer: answer = 2626
35 Correct 101 ms 118452 KB Correct answer: answer = 796
36 Correct 107 ms 118404 KB Correct answer: answer = 7580
37 Correct 109 ms 117840 KB Correct answer: answer = 1904
38 Correct 99 ms 117788 KB Correct answer: answer = 996004
39 Correct 98 ms 118072 KB Correct answer: answer = 38817
40 Correct 94 ms 118948 KB Correct answer: answer = 4096
41 Correct 120 ms 117748 KB Correct answer: answer = 1
42 Correct 85 ms 117752 KB Correct answer: answer = 1
43 Correct 90 ms 117824 KB Correct answer: answer = 2040
44 Correct 87 ms 117712 KB Correct answer: answer = 2
45 Correct 92 ms 117728 KB Correct answer: answer = 4
46 Correct 107 ms 117808 KB Correct answer: answer = 9
47 Correct 110 ms 117744 KB Correct answer: answer = 9
48 Correct 90 ms 117800 KB Correct answer: answer = 21
49 Correct 114 ms 117796 KB Correct answer: answer = 71
50 Correct 107 ms 117704 KB Correct answer: answer = 77
51 Correct 102 ms 117772 KB Correct answer: answer = 400
52 Correct 96 ms 117816 KB Correct answer: answer = 996004
53 Correct 101 ms 117748 KB Correct answer: answer = 997310
54 Correct 111 ms 117816 KB Correct answer: answer = 990781
55 Correct 92 ms 117764 KB Correct answer: answer = 996545
56 Correct 95 ms 117732 KB Correct answer: answer = 484
57 Correct 93 ms 117724 KB Correct answer: answer = 484
58 Correct 110 ms 117860 KB Correct answer: answer = 63501
59 Correct 101 ms 118140 KB Correct answer: answer = 323501
60 Correct 101 ms 118960 KB Correct answer: answer = 752500
61 Correct 109 ms 117980 KB Correct answer: answer = 761480
62 Correct 116 ms 117824 KB Correct answer: answer = 758932
63 Correct 95 ms 117784 KB Correct answer: answer = 1000000
64 Correct 102 ms 117852 KB Correct answer: answer = 750500
65 Correct 93 ms 117792 KB Correct answer: answer = 1000000
66 Correct 108 ms 117808 KB Correct answer: answer = 250000
67 Correct 102 ms 117780 KB Correct answer: answer = 250000
68 Correct 108 ms 117752 KB Correct answer: answer = 1000000
69 Correct 114 ms 117732 KB Correct answer: answer = 994009
70 Correct 112 ms 117916 KB Correct answer: answer = 59315
71 Correct 100 ms 118404 KB Correct answer: answer = 25454
72 Correct 104 ms 117720 KB Correct answer: answer = 1504
73 Correct 124 ms 117912 KB Correct answer: answer = 37486
74 Correct 122 ms 117768 KB Correct answer: answer = 4284
75 Correct 103 ms 117744 KB Correct answer: answer = 158008
76 Correct 107 ms 117748 KB Correct answer: answer = 51860
77 Correct 92 ms 117852 KB Correct answer: answer = 12985
78 Correct 102 ms 117932 KB Correct answer: answer = 997864126212
79 Correct 91 ms 117940 KB Correct answer: answer = 998608411647
80 Correct 112 ms 117936 KB Correct answer: answer = 995265560477
81 Correct 103 ms 118364 KB Correct answer: answer = 10125000
82 Correct 92 ms 118708 KB Correct answer: answer = 2291668
83 Correct 110 ms 122224 KB Correct answer: answer = 42388
84 Correct 104 ms 118008 KB Correct answer: answer = 10318
85 Correct 152 ms 118016 KB Correct answer: answer = 3416
86 Correct 96 ms 118500 KB Correct answer: answer = 331708193881
87 Correct 150 ms 118188 KB Correct answer: answer = 2861193756
88 Correct 198 ms 118248 KB Correct answer: answer = 114646930
89 Correct 154 ms 122344 KB Correct answer: answer = 9280921
90 Correct 133 ms 118224 KB Correct answer: answer = 999984053400
91 Correct 199 ms 118204 KB Correct answer: answer = 750935949134
92 Correct 110 ms 118008 KB Correct answer: answer = 1000000000000
93 Correct 94 ms 117960 KB Correct answer: answer = 998762383161
94 Correct 126 ms 122392 KB Correct answer: answer = 23017412908
95 Correct 102 ms 118048 KB Correct answer: answer = 728143410622
96 Correct 115 ms 117908 KB Correct answer: answer = 2
97 Correct 107 ms 119252 KB Correct answer: answer = 1824916
98 Correct 166 ms 118116 KB Correct answer: answer = 10680029
99 Correct 140 ms 118240 KB Correct answer: answer = 18351700
100 Correct 103 ms 118392 KB Correct answer: answer = 16040026
101 Correct 102 ms 117980 KB Correct answer: answer = 253968628325
102 Correct 156 ms 118008 KB Correct answer: answer = 10267
103 Correct 216 ms 118264 KB Correct answer: answer = 2582408
104 Correct 100 ms 118008 KB Correct answer: answer = 78024964781
105 Correct 117 ms 117980 KB Correct answer: answer = 9866346457
106 Correct 108 ms 119108 KB Correct answer: answer = 3327720949
107 Correct 108 ms 117988 KB Correct answer: answer = 86064128360
108 Correct 102 ms 118052 KB Correct answer: answer = 12698259150
109 Correct 204 ms 118148 KB Correct answer: answer = 1185259288
110 Correct 134 ms 120256 KB Correct answer: answer = 999889968863
111 Correct 122 ms 120184 KB Correct answer: answer = 999861384931
112 Correct 115 ms 120200 KB Correct answer: answer = 999811809929
113 Correct 111 ms 120176 KB Correct answer: answer = 999869756441
114 Correct 127 ms 125228 KB Correct answer: answer = 1700000000
115 Correct 288 ms 140132 KB Correct answer: answer = 131666670
116 Correct 105 ms 120244 KB Correct answer: answer = 89478486
117 Correct 274 ms 135628 KB Correct answer: answer = 4971040
118 Correct 434 ms 152088 KB Correct answer: answer = 2711494
119 Correct 1151 ms 255180 KB Correct answer: answer = 25252530
120 Correct 508 ms 156652 KB Correct answer: answer = 62500000
121 Correct 135 ms 127836 KB Correct answer: answer = 333175097780
122 Correct 330 ms 156604 KB Correct answer: answer = 33121180179
123 Correct 985 ms 255164 KB Correct answer: answer = 9802314015
124 Correct 768 ms 189584 KB Correct answer: answer = 32567551
125 Correct 1129 ms 255296 KB Correct answer: answer = 997525000000
126 Correct 850 ms 255132 KB Correct answer: answer = 752723538884
127 Correct 125 ms 120444 KB Correct answer: answer = 1000000000000
128 Correct 120 ms 120500 KB Correct answer: answer = 999978000121
129 Correct 131 ms 120488 KB Correct answer: answer = 745986144735
130 Correct 115 ms 120296 KB Correct answer: answer = 2
131 Correct 213 ms 132228 KB Correct answer: answer = 277966670
132 Correct 133 ms 125504 KB Correct answer: answer = 2500900082
133 Correct 116 ms 120444 KB Correct answer: answer = 301248349636
134 Correct 581 ms 186580 KB Correct answer: answer = 14118891
135 Correct 126 ms 120472 KB Correct answer: answer = 14384977265
136 Correct 154 ms 120420 KB Correct answer: answer = 3681368330
137 Correct 145 ms 122028 KB Correct answer: answer = 2720316816

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 117792 KB Correct answer: answer = 4
2 Correct 85 ms 117724 KB Correct answer: answer = 4
3 Correct 106 ms 117684 KB Correct answer: answer = 4
4 Correct 94 ms 117768 KB Correct answer: answer = 12
5 Correct 91 ms 117756 KB Correct answer: answer = 52
6 Correct 83 ms 117752 KB Correct answer: answer = 210
7 Correct 96 ms 117752 KB Correct answer: answer = 88
8 Correct 96 ms 117688 KB Correct answer: answer = 7696
9 Correct 101 ms 117688 KB Correct answer: answer = 1
10 Correct 107 ms 117684 KB Correct answer: answer = 2374
11 Correct 92 ms 117692 KB Correct answer: answer = 9502
12 Correct 115 ms 117732 KB Correct answer: answer = 49
13 Correct 92 ms 117792 KB Correct answer: answer = 151
14 Correct 97 ms 117788 KB Correct answer: answer = 7550
15 Correct 100 ms 117832 KB Correct answer: answer = 7220
16 Correct 89 ms 117848 KB Correct answer: answer = 7550
17 Correct 89 ms 117736 KB Correct answer: answer = 10000
18 Correct 100 ms 117752 KB Correct answer: answer = 10000
19 Correct 94 ms 117736 KB Correct answer: answer = 624
20 Correct 95 ms 117776 KB Correct answer: answer = 10000
21 Correct 114 ms 117800 KB Correct answer: answer = 1
22 Correct 103 ms 117744 KB Correct answer: answer = 4
23 Correct 97 ms 117708 KB Correct answer: answer = 1
24 Correct 103 ms 117748 KB Correct answer: answer = 5
25 Correct 86 ms 117788 KB Correct answer: answer = 41
26 Correct 96 ms 117684 KB Correct answer: answer = 71923
27 Correct 95 ms 117872 KB Correct answer: answer = 77137
28 Correct 101 ms 117852 KB Correct answer: answer = 764
29 Correct 108 ms 117772 KB Correct answer: answer = 250000
30 Correct 107 ms 117852 KB Correct answer: answer = 500
31 Correct 121 ms 117804 KB Correct answer: answer = 32
32 Correct 94 ms 117836 KB Correct answer: answer = 130050
33 Correct 99 ms 118432 KB Correct answer: answer = 5110
34 Correct 97 ms 117980 KB Correct answer: answer = 2626
35 Correct 101 ms 118452 KB Correct answer: answer = 796
36 Correct 107 ms 118404 KB Correct answer: answer = 7580
37 Correct 109 ms 117840 KB Correct answer: answer = 1904
38 Correct 99 ms 117788 KB Correct answer: answer = 996004
39 Correct 98 ms 118072 KB Correct answer: answer = 38817
40 Correct 94 ms 118948 KB Correct answer: answer = 4096
41 Correct 120 ms 117748 KB Correct answer: answer = 1
42 Correct 85 ms 117752 KB Correct answer: answer = 1
43 Correct 90 ms 117824 KB Correct answer: answer = 2040
44 Correct 87 ms 117712 KB Correct answer: answer = 2
45 Correct 92 ms 117728 KB Correct answer: answer = 4
46 Correct 107 ms 117808 KB Correct answer: answer = 9
47 Correct 110 ms 117744 KB Correct answer: answer = 9
48 Correct 90 ms 117800 KB Correct answer: answer = 21
49 Correct 114 ms 117796 KB Correct answer: answer = 71
50 Correct 107 ms 117704 KB Correct answer: answer = 77
51 Correct 102 ms 117772 KB Correct answer: answer = 400
52 Correct 96 ms 117816 KB Correct answer: answer = 996004
53 Correct 101 ms 117748 KB Correct answer: answer = 997310
54 Correct 111 ms 117816 KB Correct answer: answer = 990781
55 Correct 92 ms 117764 KB Correct answer: answer = 996545
56 Correct 95 ms 117732 KB Correct answer: answer = 484
57 Correct 93 ms 117724 KB Correct answer: answer = 484
58 Correct 110 ms 117860 KB Correct answer: answer = 63501
59 Correct 101 ms 118140 KB Correct answer: answer = 323501
60 Correct 101 ms 118960 KB Correct answer: answer = 752500
61 Correct 109 ms 117980 KB Correct answer: answer = 761480
62 Correct 116 ms 117824 KB Correct answer: answer = 758932
63 Correct 95 ms 117784 KB Correct answer: answer = 1000000
64 Correct 102 ms 117852 KB Correct answer: answer = 750500
65 Correct 93 ms 117792 KB Correct answer: answer = 1000000
66 Correct 108 ms 117808 KB Correct answer: answer = 250000
67 Correct 102 ms 117780 KB Correct answer: answer = 250000
68 Correct 108 ms 117752 KB Correct answer: answer = 1000000
69 Correct 114 ms 117732 KB Correct answer: answer = 994009
70 Correct 112 ms 117916 KB Correct answer: answer = 59315
71 Correct 100 ms 118404 KB Correct answer: answer = 25454
72 Correct 104 ms 117720 KB Correct answer: answer = 1504
73 Correct 124 ms 117912 KB Correct answer: answer = 37486
74 Correct 122 ms 117768 KB Correct answer: answer = 4284
75 Correct 103 ms 117744 KB Correct answer: answer = 158008
76 Correct 107 ms 117748 KB Correct answer: answer = 51860
77 Correct 92 ms 117852 KB Correct answer: answer = 12985
78 Correct 102 ms 117932 KB Correct answer: answer = 997864126212
79 Correct 91 ms 117940 KB Correct answer: answer = 998608411647
80 Correct 112 ms 117936 KB Correct answer: answer = 995265560477
81 Correct 103 ms 118364 KB Correct answer: answer = 10125000
82 Correct 92 ms 118708 KB Correct answer: answer = 2291668
83 Correct 110 ms 122224 KB Correct answer: answer = 42388
84 Correct 104 ms 118008 KB Correct answer: answer = 10318
85 Correct 152 ms 118016 KB Correct answer: answer = 3416
86 Correct 96 ms 118500 KB Correct answer: answer = 331708193881
87 Correct 150 ms 118188 KB Correct answer: answer = 2861193756
88 Correct 198 ms 118248 KB Correct answer: answer = 114646930
89 Correct 154 ms 122344 KB Correct answer: answer = 9280921
90 Correct 133 ms 118224 KB Correct answer: answer = 999984053400
91 Correct 199 ms 118204 KB Correct answer: answer = 750935949134
92 Correct 110 ms 118008 KB Correct answer: answer = 1000000000000
93 Correct 94 ms 117960 KB Correct answer: answer = 998762383161
94 Correct 126 ms 122392 KB Correct answer: answer = 23017412908
95 Correct 102 ms 118048 KB Correct answer: answer = 728143410622
96 Correct 115 ms 117908 KB Correct answer: answer = 2
97 Correct 107 ms 119252 KB Correct answer: answer = 1824916
98 Correct 166 ms 118116 KB Correct answer: answer = 10680029
99 Correct 140 ms 118240 KB Correct answer: answer = 18351700
100 Correct 103 ms 118392 KB Correct answer: answer = 16040026
101 Correct 102 ms 117980 KB Correct answer: answer = 253968628325
102 Correct 156 ms 118008 KB Correct answer: answer = 10267
103 Correct 216 ms 118264 KB Correct answer: answer = 2582408
104 Correct 100 ms 118008 KB Correct answer: answer = 78024964781
105 Correct 117 ms 117980 KB Correct answer: answer = 9866346457
106 Correct 108 ms 119108 KB Correct answer: answer = 3327720949
107 Correct 108 ms 117988 KB Correct answer: answer = 86064128360
108 Correct 102 ms 118052 KB Correct answer: answer = 12698259150
109 Correct 204 ms 118148 KB Correct answer: answer = 1185259288
110 Correct 134 ms 120256 KB Correct answer: answer = 999889968863
111 Correct 122 ms 120184 KB Correct answer: answer = 999861384931
112 Correct 115 ms 120200 KB Correct answer: answer = 999811809929
113 Correct 111 ms 120176 KB Correct answer: answer = 999869756441
114 Correct 127 ms 125228 KB Correct answer: answer = 1700000000
115 Correct 288 ms 140132 KB Correct answer: answer = 131666670
116 Correct 105 ms 120244 KB Correct answer: answer = 89478486
117 Correct 274 ms 135628 KB Correct answer: answer = 4971040
118 Correct 434 ms 152088 KB Correct answer: answer = 2711494
119 Correct 1151 ms 255180 KB Correct answer: answer = 25252530
120 Correct 508 ms 156652 KB Correct answer: answer = 62500000
121 Correct 135 ms 127836 KB Correct answer: answer = 333175097780
122 Correct 330 ms 156604 KB Correct answer: answer = 33121180179
123 Correct 985 ms 255164 KB Correct answer: answer = 9802314015
124 Correct 768 ms 189584 KB Correct answer: answer = 32567551
125 Correct 1129 ms 255296 KB Correct answer: answer = 997525000000
126 Correct 850 ms 255132 KB Correct answer: answer = 752723538884
127 Correct 125 ms 120444 KB Correct answer: answer = 1000000000000
128 Correct 120 ms 120500 KB Correct answer: answer = 999978000121
129 Correct 131 ms 120488 KB Correct answer: answer = 745986144735
130 Correct 115 ms 120296 KB Correct answer: answer = 2
131 Correct 213 ms 132228 KB Correct answer: answer = 277966670
132 Correct 133 ms 125504 KB Correct answer: answer = 2500900082
133 Correct 116 ms 120444 KB Correct answer: answer = 301248349636
134 Correct 581 ms 186580 KB Correct answer: answer = 14118891
135 Correct 126 ms 120472 KB Correct answer: answer = 14384977265
136 Correct 154 ms 120420 KB Correct answer: answer = 3681368330
137 Correct 145 ms 122028 KB Correct answer: answer = 2720316816
138 Correct 155 ms 122648 KB Correct answer: answer = 999976000144
139 Correct 150 ms 122672 KB Correct answer: answer = 999856102410
140 Correct 163 ms 122680 KB Correct answer: answer = 999958401531
141 Correct 145 ms 122700 KB Correct answer: answer = 999769649944
142 Correct 145 ms 122620 KB Correct answer: answer = 999874525918
143 Runtime error 335 ms 242976 KB Execution killed with signal 11 (could be triggered by violating memory limits)
144 Halted 0 ms 0 KB -