oj.uz

Submission #111343

# Submission time Handle Problem Language Result Execution time Memory
111343 2019-05-14T21:39:08 Z Benq Security Gate (JOI18_security_gate) C++14
100 / 100
 756 ms 107268 KB 
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/rope>
 
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
 
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
 
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
 
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= (a); i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define trav(a, x) for (auto& a : x)
 
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
 
#define sz(x) (int)x.size()
#define beg(x) x.begin()
#define en(x) x.end()
#define all(x) beg(x), en(x)
#define resz resize
 
const int MOD = 1000000007; // 998244353
const ll INF = 1e18;
const int MX = 100001;
const ld PI = 4*atan((ld)1);
 
template<class T> void ckmin(T &a, T b) { a = min(a, b); }
template<class T> void ckmax(T &a, T b) { a = max(a, b); }
 
namespace input {
    template<class T> void re(complex<T>& x);
    template<class T1, class T2> void re(pair<T1,T2>& p);
    template<class T> void re(vector<T>& a);
    template<class T, size_t SZ> void re(array<T,SZ>& a);
 
    template<class T> void re(T& x) { cin >> x; }
    void re(double& x) { string t; re(t); x = stod(t); }
    void re(ld& x) { string t; re(t); x = stold(t); }
    template<class Arg, class... Args> void re(Arg& first, Args&... rest) { 
        re(first); re(rest...); 
    }
 
    template<class T> void re(complex<T>& x) { T a,b; re(a,b); x = cd(a,b); }
    template<class T1, class T2> void re(pair<T1,T2>& p) { re(p.f,p.s); }
    template<class T> void re(vector<T>& a) { F0R(i,sz(a)) re(a[i]); }
    template<class T, size_t SZ> void re(array<T,SZ>& a) { F0R(i,SZ) re(a[i]); }
}
 
using namespace input;
 
namespace output {
    template<class T1, class T2> void pr(const pair<T1,T2>& x);
    template<class T, size_t SZ> void pr(const array<T,SZ>& x);
    template<class T> void pr(const vector<T>& x);
    template<class T> void pr(const set<T>& x);
    template<class T1, class T2> void pr(const map<T1,T2>& x);
 
    template<class T> void pr(const T& x) { cout << x; }
    template<class Arg, class... Args> void pr(const Arg& first, const Args&... rest) { 
        pr(first); pr(rest...); 
    }
 
    template<class T1, class T2> void pr(const pair<T1,T2>& x) { 
        pr("{",x.f,", ",x.s,"}"); 
    }
    template<class T> void prContain(const T& x) {
        pr("{");
        bool fst = 1; trav(a,x) pr(!fst?", ":"",a), fst = 0; 
        pr("}");
    }
    template<class T, size_t SZ> void pr(const array<T,SZ>& x) { prContain(x); }
    template<class T> void pr(const vector<T>& x) { prContain(x); }
    template<class T> void pr(const set<T>& x) { prContain(x); }
    template<class T1, class T2> void pr(const map<T1,T2>& x) { prContain(x); }
    
    void ps() { pr("\n"); } 
    template<class Arg, class... Args> void ps(const Arg& first, const Args&... rest) { 
        pr(first," "); ps(rest...); // print w/ spaces
    }
}
 
using namespace output;
 
namespace io {
    void setIn(string s) { freopen(s.c_str(),"r",stdin); }
    void setOut(string s) { freopen(s.c_str(),"w",stdout); }
    void setIO(string s = "") {
        ios_base::sync_with_stdio(0); cin.tie(0); // fast I/O
        if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
    }
}
 
using namespace io;
 
template<class T> T invGeneral(T a, T b) {
    a %= b; if (a == 0) return b == 1 ? 0 : -1;
    T x = invGeneral(b,a); 
    return x == -1 ? -1 : ((1-(ll)b*x)/a+b)%b;
}
 
template<class T> struct modular {
    T val; 
    explicit operator T() const { return val; }
    modular() { val = 0; }
    template<class U> modular(const U& v) {
        val = (-MOD <= v && v <= MOD) ? v : v % MOD;
        if (val < 0) val += MOD;
    }
    friend ostream& operator<<(ostream& os, const modular& a) { return os << a.val; }
    friend bool operator==(const modular& a, const modular& b) { return a.val == b.val; }
    friend bool operator!=(const modular& a, const modular& b) { return !(a == b); }
 
    modular operator-() const { return modular(-val); }
    modular& operator+=(const modular& m) { if ((val += m.val) >= MOD) val -= MOD; return *this; }
    modular& operator-=(const modular& m) { if ((val -= m.val) < 0) val += MOD; return *this; }
    modular& operator*=(const modular& m) { val = (ll)val*m.val%MOD; return *this; }
    friend modular exp(modular a, ll p) {
        modular ans = 1; for (; p; p /= 2, a *= a) if (p&1) ans *= a;
        return ans;
    }
    friend modular inv(const modular& a) { return invGeneral(a.val,MOD); } 
    // inv is equivalent to return exp(b,b.mod-2) if prime
    modular& operator/=(const modular& m) { return (*this) *= inv(m); }
    
    friend modular operator+(modular a, const modular& b) { return a += b; }
    friend modular operator-(modular a, const modular& b) { return a -= b; }
    friend modular operator*(modular a, const modular& b) { return a *= b; }
    
    friend modular operator/(modular a, const modular& b) { return a /= b; }
};
 
typedef modular<int> mi;
typedef pair<mi,mi> pmi;
typedef vector<mi> vmi;
typedef vector<pmi> vpmi;
 
int N;
string S;
mi ans(0);
mi DP[301][301][301];

void gen() {
    F0R(i,sz(S)+1) F0R(j,sz(S)+1) F0R(k,sz(S)+1) DP[i][j][k] = 0;
    DP[sz(S)][0][0] = 1;
    F0Rd(i,sz(S)) {
        char c = S[i];
        F0R(j,sz(S)) FOR(k,j,sz(S)) {
            int e = (int)DP[i+1][j][k];
            if (!e) continue;
            if (c != ')') {
                if (j) DP[i][j-1][k] += e;
            }
            if (c != '(') {
                DP[i][j+1][max(k,j+1)] += e;
            }
        }
    }
    F0R(i,sz(S)+1) F0Rd(j,sz(S)) DP[i][0][j] += DP[i][0][j+1];
}

mi finish(int pos, int need) {
    if (need > sz(S)) return 0;
    /*assert(need >= 0);
    mi res(0); FOR(i,need,sz(S)+1) res += DP[pos][0][i];*/
    // ps("WAT",pos,need,res);
    return DP[pos][0][need];
}
 
void tri(int A, int t) {
    // max1 <= max2-d
    // all in first prefix <= max1 
    // need smth >= t+d in second 
    
    // 0: not yet < 0, not found t 
    // 1: not yet < 0, found t 
    // 2: < 0, but never > 2t
        // if 2d-1 -> 2d maybe go to 3 
    // 3: not found smth >= max1+d 
    // 4: found smth >= max1+d 
    // end: = 2d
    
    // ps("HUH",A,t);
    array<array<mi,3>,601> cur = array<array<mi,3>,601>();
    array<array<mi,3>,601> tmp = array<array<mi,3>,601>();
    cur[N][0 >= A] = 1;
    int par = 0;
    F0R(pos,sz(S)) {
        char c = S[pos];
    	F0R(i,601) F0R(j,3) tmp[i][j] = 0;
        FOR(i,-N,N+1) if ((i-par) % 2 == 0) {
            int e = (int)cur[N+i][0];
            if (e) {
                if (c != ')') tmp[N+i+1][i+1 == A] += e;
                if (c != '(' && i) tmp[N+i-1][0] += e;
            }
            e = (int)cur[N+i][1];
            if (e) {
                if (c != ')' && i+1 <= A) tmp[N+i+1][1] += e;
                if (c != '(') tmp[N+i-1][1+(i == 0)] += e;
            }
            e = (int)cur[N+i][2];
            if (e) {
                if (c != ')') {
                    if (i+1 <= 2*A) {
                    	if ((i-1) % 2 == 0) {
                    		int C = i+1; int B = A+C/2;
                    		ans += e*finish(pos+1,B-C+t);
                    	}
                        tmp[N+i+1][2] += e;
                    }
                } 
                if (c != '(') tmp[N+i-1][2] += e;
            }
        }
        swap(cur,tmp);
        // ps("??",A,t,pos,cur[N-1][2]);
        par ^= 1;
    }
}

void cool(int A) {
    // keep track of current mx: 2*d, current sum 
        // 0: not found 
        // 1: everything must <= 2*(mx-d) until you get to mx-d 
        // 2: found
        
    // csum, mx
    // found A without any > 2*A after 
    // 2d-1 -> 2d <= 2*A 
    array<array<mi,2>,301> cur = array<array<mi,2>,301>();
    array<array<mi,2>,301> tmp = array<array<mi,2>,301>();
    cur[0][0] = 1; int par = 0; 
    F0R(pos,sz(S)) {
        char c = S[pos];
    	F0R(i,301) F0R(j,2) tmp[i][j] = 0;
        F0R(i,N+1) if ((i-par) % 2 == 0) {
            int e = (int)cur[i][0];
            if (e) {
                if (c != ')') {
                    if ((i+1) % 2 == 0 && (i+1 == A || A >= (i+1))) {
                        int C = i+1; int B = A+C/2;
                		ans += e*(finish(pos+1,B-C)-finish(pos+1,B-C+1));
                    }
                    tmp[i+1][(i+1) == A] += e;
                }
                if (c != '(' && i) tmp[i-1][i-1 == A] += e;
            }
            e = (int)cur[i][1];
            if (e) {
                if (c != ')') {
                    if ((i+1) % 2 == 0) {
                        // ps("WAT");
                        int C = i+1; int B = A+C/2;
                		ans += e*(finish(pos+1,B-C)-finish(pos+1,B-C+1));
                    }
                    tmp[i+1][(i+1) <= 2*A] += e;
                } 
                if (c != '(' && i) tmp[i-1][1] += e;
            }
        }
        swap(cur,tmp); // ps("??",A,t,pos,cur[N-1][2]);
        par ^= 1;
    }
}

void balanced() {
    array<mi,301> cur = array<mi,301>(); cur[0] = 1;
    trav(c,S) {
        array<mi,301> tmp = array<mi,301>();
        F0R(i,N+1) {
            int e = (int)cur[i];
            if (e) {
                if (c != ')') tmp[i+1] += e;
                if (c != '(' && i) tmp[i-1] += e;
            }
        }
        swap(cur,tmp);
    }
    // ps("??",cur[0]);
    ans += cur[0];
}

int main() {
    setIO(); re(N,S); assert(sz(S) == N);
    if (N&1) { ps(0); exit(0); }
    // N = 10;
    F0R(i,1) {
        /*ans = 0; S = "";
        F0R(j,N) {
            if (i&(1<<j)) S += '(';
            else S += ')';
        }*/
        balanced();
        gen();
        F0R(i,N/2+1) tri(i,0);
        FOR(i,1,N/2+1) cool(i);
        reverse(all(S));
        trav(t,S) {
            if (t == '(') t = ')';
            else if (t == ')') t = '(';
        }
        gen();
        F0R(i,N/2+1) tri(i,1);
        FOR(i,1,N/2+1) cool(i);
        ps(ans);
    }
}
 
/* stuff you should look for
    * int overflow, array bounds
    * special cases (n=1?), set tle
    * do smth instead of nothing and stay organized
*/

Compilation message

securitygate.cpp: In function 'void io::setIn(std::__cxx11::string)':
securitygate.cpp:112:35: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     void setIn(string s) { freopen(s.c_str(),"r",stdin); }
                            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
securitygate.cpp: In function 'void io::setOut(std::__cxx11::string)':
securitygate.cpp:113:36: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     void setOut(string s) { freopen(s.c_str(),"w",stdout); }
                             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 107000 KB Output is correct
2 Correct 159 ms 107128 KB Output is correct
3 Correct 125 ms 107128 KB Output is correct
4 Correct 133 ms 107128 KB Output is correct
5 Correct 122 ms 107128 KB Output is correct
6 Correct 126 ms 107004 KB Output is correct
7 Correct 132 ms 107004 KB Output is correct
8 Correct 159 ms 107120 KB Output is correct
9 Correct 152 ms 107128 KB Output is correct
10 Correct 156 ms 107128 KB Output is correct
11 Correct 132 ms 107128 KB Output is correct
12 Correct 143 ms 107056 KB Output is correct
13 Correct 135 ms 107056 KB Output is correct
14 Correct 139 ms 107256 KB Output is correct
15 Correct 157 ms 107048 KB Output is correct
16 Correct 155 ms 107040 KB Output is correct
17 Correct 152 ms 107060 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 107000 KB Output is correct
2 Correct 159 ms 107128 KB Output is correct
3 Correct 125 ms 107128 KB Output is correct
4 Correct 133 ms 107128 KB Output is correct
5 Correct 122 ms 107128 KB Output is correct
6 Correct 126 ms 107004 KB Output is correct
7 Correct 132 ms 107004 KB Output is correct
8 Correct 159 ms 107120 KB Output is correct
9 Correct 152 ms 107128 KB Output is correct
10 Correct 156 ms 107128 KB Output is correct
11 Correct 132 ms 107128 KB Output is correct
12 Correct 143 ms 107056 KB Output is correct
13 Correct 135 ms 107056 KB Output is correct
14 Correct 139 ms 107256 KB Output is correct
15 Correct 157 ms 107048 KB Output is correct
16 Correct 155 ms 107040 KB Output is correct
17 Correct 152 ms 107060 KB Output is correct
18 Correct 131 ms 107044 KB Output is correct
19 Correct 156 ms 107000 KB Output is correct
20 Correct 120 ms 107000 KB Output is correct
21 Correct 152 ms 107120 KB Output is correct
22 Correct 160 ms 107128 KB Output is correct
23 Correct 165 ms 107128 KB Output is correct
24 Correct 174 ms 107128 KB Output is correct
25 Correct 151 ms 107132 KB Output is correct
26 Correct 129 ms 107000 KB Output is correct
27 Correct 142 ms 107000 KB Output is correct
28 Correct 123 ms 107100 KB Output is correct
29 Correct 165 ms 107024 KB Output is correct
30 Correct 158 ms 107000 KB Output is correct
31 Correct 162 ms 107076 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 107000 KB Output is correct
2 Correct 159 ms 107128 KB Output is correct
3 Correct 125 ms 107128 KB Output is correct
4 Correct 133 ms 107128 KB Output is correct
5 Correct 122 ms 107128 KB Output is correct
6 Correct 126 ms 107004 KB Output is correct
7 Correct 132 ms 107004 KB Output is correct
8 Correct 159 ms 107120 KB Output is correct
9 Correct 152 ms 107128 KB Output is correct
10 Correct 156 ms 107128 KB Output is correct
11 Correct 132 ms 107128 KB Output is correct
12 Correct 143 ms 107056 KB Output is correct
13 Correct 135 ms 107056 KB Output is correct
14 Correct 139 ms 107256 KB Output is correct
15 Correct 157 ms 107048 KB Output is correct
16 Correct 155 ms 107040 KB Output is correct
17 Correct 152 ms 107060 KB Output is correct
18 Correct 131 ms 107044 KB Output is correct
19 Correct 156 ms 107000 KB Output is correct
20 Correct 120 ms 107000 KB Output is correct
21 Correct 152 ms 107120 KB Output is correct
22 Correct 160 ms 107128 KB Output is correct
23 Correct 165 ms 107128 KB Output is correct
24 Correct 174 ms 107128 KB Output is correct
25 Correct 151 ms 107132 KB Output is correct
26 Correct 129 ms 107000 KB Output is correct
27 Correct 142 ms 107000 KB Output is correct
28 Correct 123 ms 107100 KB Output is correct
29 Correct 165 ms 107024 KB Output is correct
30 Correct 158 ms 107000 KB Output is correct
31 Correct 162 ms 107076 KB Output is correct
32 Correct 122 ms 107100 KB Output is correct
33 Correct 123 ms 107100 KB Output is correct
34 Correct 134 ms 107128 KB Output is correct
35 Correct 128 ms 107052 KB Output is correct
36 Correct 161 ms 107000 KB Output is correct
37 Correct 163 ms 107000 KB Output is correct
38 Correct 163 ms 107116 KB Output is correct
39 Correct 124 ms 107112 KB Output is correct
40 Correct 153 ms 107116 KB Output is correct
41 Correct 143 ms 107232 KB Output is correct
42 Correct 162 ms 107092 KB Output is correct
43 Correct 153 ms 107004 KB Output is correct
44 Correct 180 ms 107100 KB Output is correct
45 Correct 158 ms 107000 KB Output is correct

Subtask #4
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 107000 KB Output is correct
2 Correct 159 ms 107128 KB Output is correct
3 Correct 125 ms 107128 KB Output is correct
4 Correct 133 ms 107128 KB Output is correct
5 Correct 122 ms 107128 KB Output is correct
6 Correct 126 ms 107004 KB Output is correct
7 Correct 132 ms 107004 KB Output is correct
8 Correct 159 ms 107120 KB Output is correct
9 Correct 152 ms 107128 KB Output is correct
10 Correct 156 ms 107128 KB Output is correct
11 Correct 132 ms 107128 KB Output is correct
12 Correct 143 ms 107056 KB Output is correct
13 Correct 135 ms 107056 KB Output is correct
14 Correct 139 ms 107256 KB Output is correct
15 Correct 157 ms 107048 KB Output is correct
16 Correct 155 ms 107040 KB Output is correct
17 Correct 152 ms 107060 KB Output is correct
18 Correct 131 ms 107044 KB Output is correct
19 Correct 156 ms 107000 KB Output is correct
20 Correct 120 ms 107000 KB Output is correct
21 Correct 152 ms 107120 KB Output is correct
22 Correct 160 ms 107128 KB Output is correct
23 Correct 165 ms 107128 KB Output is correct
24 Correct 174 ms 107128 KB Output is correct
25 Correct 151 ms 107132 KB Output is correct
26 Correct 129 ms 107000 KB Output is correct
27 Correct 142 ms 107000 KB Output is correct
28 Correct 123 ms 107100 KB Output is correct
29 Correct 165 ms 107024 KB Output is correct
30 Correct 158 ms 107000 KB Output is correct
31 Correct 162 ms 107076 KB Output is correct
32 Correct 122 ms 107100 KB Output is correct
33 Correct 123 ms 107100 KB Output is correct
34 Correct 134 ms 107128 KB Output is correct
35 Correct 128 ms 107052 KB Output is correct
36 Correct 161 ms 107000 KB Output is correct
37 Correct 163 ms 107000 KB Output is correct
38 Correct 163 ms 107116 KB Output is correct
39 Correct 124 ms 107112 KB Output is correct
40 Correct 153 ms 107116 KB Output is correct
41 Correct 143 ms 107232 KB Output is correct
42 Correct 162 ms 107092 KB Output is correct
43 Correct 153 ms 107004 KB Output is correct
44 Correct 180 ms 107100 KB Output is correct
45 Correct 158 ms 107000 KB Output is correct
46 Correct 118 ms 107100 KB Output is correct
47 Correct 163 ms 107108 KB Output is correct
48 Correct 136 ms 107060 KB Output is correct
49 Correct 151 ms 107000 KB Output is correct
50 Correct 142 ms 107060 KB Output is correct
51 Correct 127 ms 107000 KB Output is correct
52 Correct 143 ms 107072 KB Output is correct
53 Correct 165 ms 107028 KB Output is correct
54 Correct 158 ms 107096 KB Output is correct
55 Correct 163 ms 107268 KB Output is correct
56 Correct 127 ms 107128 KB Output is correct
57 Correct 129 ms 107000 KB Output is correct
58 Correct 125 ms 107128 KB Output is correct
59 Correct 169 ms 107228 KB Output is correct
60 Correct 180 ms 107128 KB Output is correct
61 Correct 159 ms 107256 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 107000 KB Output is correct
2 Correct 159 ms 107128 KB Output is correct
3 Correct 125 ms 107128 KB Output is correct
4 Correct 133 ms 107128 KB Output is correct
5 Correct 122 ms 107128 KB Output is correct
6 Correct 126 ms 107004 KB Output is correct
7 Correct 132 ms 107004 KB Output is correct
8 Correct 159 ms 107120 KB Output is correct
9 Correct 152 ms 107128 KB Output is correct
10 Correct 156 ms 107128 KB Output is correct
11 Correct 132 ms 107128 KB Output is correct
12 Correct 143 ms 107056 KB Output is correct
13 Correct 135 ms 107056 KB Output is correct
14 Correct 139 ms 107256 KB Output is correct
15 Correct 157 ms 107048 KB Output is correct
16 Correct 155 ms 107040 KB Output is correct
17 Correct 152 ms 107060 KB Output is correct
18 Correct 131 ms 107044 KB Output is correct
19 Correct 156 ms 107000 KB Output is correct
20 Correct 120 ms 107000 KB Output is correct
21 Correct 152 ms 107120 KB Output is correct
22 Correct 160 ms 107128 KB Output is correct
23 Correct 165 ms 107128 KB Output is correct
24 Correct 174 ms 107128 KB Output is correct
25 Correct 151 ms 107132 KB Output is correct
26 Correct 129 ms 107000 KB Output is correct
27 Correct 142 ms 107000 KB Output is correct
28 Correct 123 ms 107100 KB Output is correct
29 Correct 165 ms 107024 KB Output is correct
30 Correct 158 ms 107000 KB Output is correct
31 Correct 162 ms 107076 KB Output is correct
32 Correct 122 ms 107100 KB Output is correct
33 Correct 123 ms 107100 KB Output is correct
34 Correct 134 ms 107128 KB Output is correct
35 Correct 128 ms 107052 KB Output is correct
36 Correct 161 ms 107000 KB Output is correct
37 Correct 163 ms 107000 KB Output is correct
38 Correct 163 ms 107116 KB Output is correct
39 Correct 124 ms 107112 KB Output is correct
40 Correct 153 ms 107116 KB Output is correct
41 Correct 143 ms 107232 KB Output is correct
42 Correct 162 ms 107092 KB Output is correct
43 Correct 153 ms 107004 KB Output is correct
44 Correct 180 ms 107100 KB Output is correct
45 Correct 158 ms 107000 KB Output is correct
46 Correct 118 ms 107100 KB Output is correct
47 Correct 163 ms 107108 KB Output is correct
48 Correct 136 ms 107060 KB Output is correct
49 Correct 151 ms 107000 KB Output is correct
50 Correct 142 ms 107060 KB Output is correct
51 Correct 127 ms 107000 KB Output is correct
52 Correct 143 ms 107072 KB Output is correct
53 Correct 165 ms 107028 KB Output is correct
54 Correct 158 ms 107096 KB Output is correct
55 Correct 163 ms 107268 KB Output is correct
56 Correct 127 ms 107128 KB Output is correct
57 Correct 129 ms 107000 KB Output is correct
58 Correct 125 ms 107128 KB Output is correct
59 Correct 169 ms 107228 KB Output is correct
60 Correct 180 ms 107128 KB Output is correct
61 Correct 159 ms 107256 KB Output is correct
62 Correct 383 ms 107196 KB Output is correct
63 Correct 342 ms 107176 KB Output is correct
64 Correct 287 ms 107004 KB Output is correct
65 Correct 201 ms 107128 KB Output is correct
66 Correct 700 ms 107128 KB Output is correct
67 Correct 537 ms 107176 KB Output is correct
68 Correct 756 ms 107128 KB Output is correct
69 Correct 284 ms 107128 KB Output is correct
70 Correct 283 ms 107192 KB Output is correct
71 Correct 174 ms 107160 KB Output is correct
72 Correct 207 ms 107100 KB Output is correct
73 Correct 620 ms 107268 KB Output is correct
74 Correct 624 ms 107128 KB Output is correct