Submission #896079

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
896079	2023-12-31T17:32:19 Z	tfgs	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	37 ms	15360 KB

triusis

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using db = long double; // or double, if TL is tight
using str = string; // yay python! 

// pairs
using pi = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;
#define mp make_pair
#define f first
#define s second

#define tcT template<class T
#define tcTU tcT, class U
// ^ lol this makes everything look weird but I'll try it
tcT> using V = vector<T>; 
tcT, size_t SZ> using AR = array<T,SZ>; 
using vi = V<int>;
using vb = V<bool>;
using vl = V<ll>;
using vd = V<db>;
using vs = V<str>;
using vpi = V<pi>;
using vpl = V<pl>;
using vpd = V<pd>;

// vectors
// oops size(x), rbegin(x), rend(x) need C++17
#define sz(x) ll((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) x.rbegin(), x.rend() 
#define sor(x) sort(all(x)) 
#define rsz resize
#define ins insert 
#define pb push_back
#define eb emplace_back
#define ft front()
#define bk back()

#define lb lower_bound
#define ub upper_bound
tcT> ll lwb(V<T>& a, const T& b) { return ll(lb(all(a),b)-bg(a)); }
tcT> ll upb(V<T>& a, const T& b) { return ll(ub(all(a),b)-bg(a)); }

// loops
#define FOR(i,a,b) for (ll i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define F1R(i,a) FOR(i,1,a+1)
#define ROF(i,a,b) for (ll i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define R1F(i,a) ROF(i,1,a+1)
#define rep(a) F0R(_,a)
#define each(a,x) for (auto& a: x)

const ll P = 1e9+7; // 998244353;
const ll MX = 2e5+5;
const ll BIG = 1e18; // not too close to LLONG_MAX
const db PI = acos((db)-1);
const ll dx[4]{1,0,-1,0}, dy[4]{0,1,0,-1}; // for every grid problem!!
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 
template<class T> using pqg = priority_queue<T,vector<T>,greater<T>>;

ll binpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % P;
        b >>= 1;
        a = a * a % P;
    }

    return res;
}

// bitwise ops
// also see https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
constexpr ll pct(ll x) { return __builtin_popcount(x); } // # of bits set
constexpr ll bits(ll x) { // assert(x >= 0); // make C++11 compatible until USACO updates ...
    return x == 0 ? 0 : 31-__builtin_clz(x); } // floor(log2(x)) 
constexpr ll p2(ll x) { return 1<<x; }
constexpr ll msk2(ll x) { return p2(x)-1; }

ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down

tcT> bool ckmin(T& a, const T& b) {
    return b < a ? a = b, 1 : 0; } // set a = min(a,b)
tcT> bool ckmax(T& a, const T& b) {
    return a < b ? a = b, 1 : 0; } // set a = max(a,b)

tcTU> T fstTrue(T lo, T hi, U f) {
    ++hi; assert(lo <= hi); // assuming f is increasing
    while (lo < hi) { // find first index such that f is true 
        T mid = lo+(hi-lo)/2;
        f(mid) ? hi = mid : lo = mid+1; 
    } 
    return lo;
}
tcTU> T lstTrue(T lo, T hi, U f) {
    --lo; assert(lo <= hi); // assuming f is decreasing
    while (lo < hi) { // find first index such that f is true 
        T mid = lo+(hi-lo+1)/2;
        f(mid) ? lo = mid : hi = mid-1;
    } 
    return lo;
}
tcT> void UNIQUE(vector<T>& v) { // sort and remove duplicates
    sort(all(v)); v.erase(unique(all(v)),end(v)); }
tcTU> void erase(T& t, const U& u) { // don't erase
    auto it = t.find(u); assert(it != end(t));
    t.erase(it); } // element that doesn't exist from (multi)set

#define tcTUU tcT, class ...U

inline namespace Helpers {
    //////////// is_iterable
    // https://stackoverflow.com/questions/13830158/check-if-a-variable-type-is-iterable
    // this gets used only when we can call begin() and end() on that type
    tcT, class = void> struct is_iterable : false_type {};
    tcT> struct is_iterable<T, void_t<decltype(begin(declval<T>())),
                                                                                                                                            decltype(end(declval<T>()))
                                                                                                                                        >
                                                                                                > : true_type {};
    tcT> constexpr bool is_iterable_v = is_iterable<T>::value;

    //////////// is_readable
    tcT, class = void> struct is_readable : false_type {};
    tcT> struct is_readable<T,
                                    typename std::enable_if_t<
                                                    is_same_v<decltype(cin >> declval<T&>()), istream&>
                                    >
                    > : true_type {};
    tcT> constexpr bool is_readable_v = is_readable<T>::value;

    //////////// is_printable
    // // https://nafe.es/posts/2020-02-29-is-printable/
    tcT, class = void> struct is_printable : false_type {};
    tcT> struct is_printable<T,
                                    typename std::enable_if_t<
                                                    is_same_v<decltype(cout << declval<T>()), ostream&>
                                    >
                    > : true_type {};
    tcT> constexpr bool is_printable_v = is_printable<T>::value;
}

inline namespace Input {
    tcT> constexpr bool needs_input_v = !is_readable_v<T> && is_iterable_v<T>;
    tcTUU> void re(T& t, U&... u);
    tcTU> void re(pair<T,U>& p); // pairs

    // re: read
    tcT> typename enable_if<is_readable_v<T>,void>::type re(T& x) { cin >> x; } // default
    tcT> void re(complex<T>& c) { T a,b; re(a,b); c = {a,b}; } // complex
    tcT> typename enable_if<needs_input_v<T>,void>::type re(T& i); // ex. vectors, arrays
    tcTU> void re(pair<T,U>& p) { re(p.f,p.s); }
    tcT> typename enable_if<needs_input_v<T>,void>::type re(T& i) {
        each(x,i) re(x); }
    tcTUU> void re(T& t, U&... u) { re(t); re(u...); } // read multiple

    // rv: resize and read vectors
    void rv(size_t) {}
    tcTUU> void rv(size_t N, V<T>& t, U&... u);
    template<class...U> void rv(size_t, size_t N2, U&... u);
    tcTUU> void rv(size_t N, V<T>& t, U&... u) {
        t.rsz(N); re(t);
        rv(N,u...); }
    template<class...U> void rv(size_t, size_t N2, U&... u) {
        rv(N2,u...); }

    // dumb shortcuts to read in ints
    void decrement() {} // subtract one from each
    tcTUU> void decrement(T& t, U&... u) { --t; decrement(u...); }
    #define ints(...) int __VA_ARGS__; re(__VA_ARGS__);
    #define int1(...) ints(__VA_ARGS__); decrement(__VA_ARGS__);
}

inline namespace ToString {
    tcT> constexpr bool needs_output_v = !is_printable_v<T> && is_iterable_v<T>;

    // ts: string representation to print
    tcT> typename enable_if<is_printable_v<T>,str>::type ts(T v) {
        stringstream ss; ss << fixed << setprecision(15) << v;
        return ss.str(); } // default
    tcT> str bit_vec(T t) { // bit vector to string
        str res = "{"; F0R(i,sz(t)) res += ts(t[i]);
        res += "}"; return res; }
    str ts(V<bool> v) { return bit_vec(v); }
    template<size_t SZ> str ts(bitset<SZ> b) { return bit_vec(b); } // bit vector
    tcTU> str ts(pair<T,U> p); // pairs
    tcT> typename enable_if<needs_output_v<T>,str>::type ts(T v); // vectors, arrays
    tcTU> str ts(pair<T,U> p) { return "("+ts(p.f)+", "+ts(p.s)+")"; }
    tcT> typename enable_if<is_iterable_v<T>,str>::type ts_sep(T v, str sep) {
        // convert container to string w/ separator sep
        bool fst = 1; str res = "";
        for (const auto& x: v) {
            if (!fst) res += sep;
            fst = 0; res += ts(x);
        }
        return res;
    }
    tcT> typename enable_if<needs_output_v<T>,str>::type ts(T v) {
        return "{"+ts_sep(v,", ")+"}"; }

    // for nested DS
    template<int, class T> typename enable_if<!needs_output_v<T>,vs>::type 
            ts_lev(const T& v) { return {ts(v)}; }
    template<int lev, class T> typename enable_if<needs_output_v<T>,vs>::type 
            ts_lev(const T& v) {
        if (lev == 0 || !sz(v)) return {ts(v)};
        vs res;
        for (const auto& t: v) {
            if (sz(res)) res.bk += ",";
            vs tmp = ts_lev<lev-1>(t);
            res.ins(end(res),all(tmp));
        }
        F0R(i,sz(res)) {
            str bef = " "; if (i == 0) bef = "{";
            res[i] = bef+res[i];
        }
        res.bk += "}";
        return res;
    }
}

inline namespace Output {
    template<class T> void pr_sep(ostream& os, str, const T& t) { os << ts(t); }
    template<class T, class... U> void pr_sep(ostream& os, str sep, const T& t, const U&... u) {
        pr_sep(os,sep,t); os << sep; pr_sep(os,sep,u...); }
    // print w/ no spaces
    template<class ...T> void pr(const T&... t) { pr_sep(cout,"",t...); } 
    // print w/ spaces, end with newline
    void ps() { cout << "\n"; }
    template<class ...T> void ps(const T&... t) { pr_sep(cout," ",t...); ps(); } 
    // debug to cerr
    template<class ...T> void dbg_out(const T&... t) {
        pr_sep(cerr," | ",t...); cerr << endl; }
    void loc_info(int line, str names) {
        cerr << "Line(" << line << ") -> [" << names << "]: "; }
    template<int lev, class T> void dbgl_out(const T& t) {
        cerr << "\n\n" << ts_sep(ts_lev<lev>(t),"\n") << "\n" << endl; }
    #ifdef I_AM_NOOB
        #define gg(...) loc_info(__LINE__,#__VA_ARGS__), dbg_out(__VA_ARGS__)
        #define ggl(lev,x) loc_info(__LINE__,#x), dbgl_out<lev>(x)
    #else // don't actually submit with this
        #define gg(...) 777771449
        #define ggl(lev,x)
    #endif

    // https://stackoverflow.com/questions/47980498/accurate-c-c-clock-on-a-multi-core-processor-with-auto-overclock?noredirect=1&lq=1
    const auto beg = std::chrono::high_resolution_clock::now();
    void dbg_time() {
        auto duration = chrono::duration<double>(
            std::chrono::high_resolution_clock::now() - beg);
        gg(duration.count());
    }
}

inline namespace FileIO {
    void setIn(str s)  { freopen(s.c_str(),"r",stdin); }
    void setOut(str s) { freopen(s.c_str(),"w",stdout); }
    void setIO(str s = "") {
        cin.tie(0)->sync_with_stdio(0); // unsync C / C++ I/O streams
        // cin.exceptions(cin.failbit);
        // throws exception when do smth illegal
        // ex. try to read letter into int
        if (sz(s) && fopen((s+".in").c_str(), "r")) setIn(s+".in"), setOut(s+".out"); // for old USACO
    }
}

// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html
template<class Fun> class y_combinator_result {
    Fun fun_;
public:
    template<class T> explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
    template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); }
};
template<class Fun> decltype(auto) yy(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }

struct chash {
    // any random-ish large odd number will do
    const uint64_t C = uint64_t(2e18 * PI) + 71;
    // random 32-bit number
    const uint32_t RANDOM =
                    chrono::steady_clock::now().time_since_epoch().count();
    size_t operator()(uint64_t x) const {
        // see https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
        return __builtin_bswap64((x ^ RANDOM) * C);
    }
};
template <class K, class V> using cmap = unordered_map<K, V, chash>;
// example usage: cmap<int, int>

const ll N = 1e6+2;
ll a[N];
struct node {
    node *l, *r;
    ll v;
    node(node* tl, node* tr) {
        l = tl;
        r = tr;
        v = max(tl->v, tr->v);
    }
    node(ll x) {
        l = r = nullptr;
        v = x;
    }
};
node* build(ll tl, ll tr) {
    if (tl == tr - 1) return new node(a[tl]);
    else {
        ll tm = (tl + tr) / 2;
        return new node(build(tl, tm), build(tm, tr));
    }
};
ll query(node* t, ll tl, ll tr, ll l, ll r) {
    if (l >= r) return 0;
    if (tl == l && tr == r) return t->v;
    ll tm = (tl + tr) / 2;
    ll r1 = query(t->l, tl, tm, l, min(r, tm));
    ll r2 = query(t->r, tm, tr, max(l, tm), r);
    return max(r1, r2);
}
void upd(node*t, ll tl, ll tr, ll p, ll x) {
    if (tl == tr-1) {
        a[tl] = x;
        return;
    }
    ll tm = (tl+tr)/2;
    if (p <= tm) upd(t->l, tl, tm, p, x);
    else upd(t->r, tm+1, tr, p, x);
}

// BeginCodeSnip{Range Maximum Segment Tree}
class MaxSegTree {
  private:
	int len;
	vector<int> segtree;

  public:
	MaxSegTree(int len) : len(len), segtree(2 * len) {}

	void set(int ind, int val) {
		for (segtree[ind += len] = val; ind > 1; ind >>= 1) {
			segtree[ind >> 1] = max(segtree[ind], segtree[ind ^ 1]);
		}
	}

	// maximum of the range [from, to)
	int range_max(int from, int to) {
		int max_ = INT32_MIN;
		for (from += len, to += len; from < to; from >>= 1, to >>= 1) {
			if ((from & 1) != 0) { max_ = max(max_, segtree[from++]); }
			if ((to & 1) != 0) { max_ = max(max_, segtree[--to]); }
		}
		return max_;
	}
};
// EndCodeSnip

void solve() {
    ll n, m; re(n, m);
    vl a(n+1); F1R(i, n) re(a[i]);
    F1R(i, n) a[i] -= m*i;
    // ps(a);

    V<vl> L;
    FOR(i, 1, n+1) if (a[i] <= 0) {
        if (!sz(L)) {
            L.pb({ a[i] });
            continue;
        }

        auto x = fstTrue(all(L)-1, [&](auto v) {
            return (*v).bk < a[i];
        });
        if (x == end(L)) {
            L.pb({a[i]});
        } else {
            (*x).pb(a[i]);
        }

        // ps(L);
    }

    ps(n-sz(L));

    // auto tr = MaxSegTree(N);
    // ll ans = 0;
    // FOR(i, 1, n+1) if (a[i] <= 0) {
        // ll x = tr.range_max(a[i], N)+1;
        // ckmax(ans, x);
        // tr.set(a[i], x);
        // gg(x);
    // }

    // ps(n-ans);

    // node* tr = build(0, N);
    // F0R(i, n) {
        // ll mx = query(tr, 0, N, max(a[i]-m, 0ll), N);
        // upd(tr, 0, N, a[i], mx+1);
    // }

    // ll best = query(tr, 0, N, 0, N);
    // ps(n-best);
}

signed main() {
    setIO();
    
    solve(); 

    return 0;
}

Compilation message

triusis.cpp: In function 'void Output::dbg_time()':
triusis.cpp:248:25: warning: statement has no effect [-Wunused-value]
  248 |         #define gg(...) 777771449
      |                         ^~~~~~~~~
triusis.cpp:257:9: note: in expansion of macro 'gg'
  257 |         gg(duration.count());
      |         ^~
triusis.cpp: In function 'void FileIO::setIn(str)':
triusis.cpp:262:33: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  262 |     void setIn(str s)  { freopen(s.c_str(),"r",stdin); }
      |                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
triusis.cpp: In function 'void FileIO::setOut(str)':
triusis.cpp:263:33: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  263 |     void setOut(str s) { freopen(s.c_str(),"w",stdout); }
      |                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	344 KB	Output is correct
13	Correct	0 ms	344 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct

Subtask #2

21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	344 KB	Output is correct
13	Correct	0 ms	344 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	1 ms	604 KB	Output is correct
21	Correct	1 ms	860 KB	Output is correct
22	Correct	1 ms	348 KB	Output is correct
23	Correct	1 ms	860 KB	Output is correct
24	Correct	1 ms	860 KB	Output is correct
25	Correct	1 ms	764 KB	Output is correct
26	Correct	1 ms	860 KB	Output is correct
27	Correct	1 ms	604 KB	Output is correct
28	Correct	1 ms	740 KB	Output is correct
29	Correct	1 ms	860 KB	Output is correct
30	Correct	1 ms	736 KB	Output is correct
31	Correct	1 ms	856 KB	Output is correct
32	Correct	1 ms	736 KB	Output is correct
33	Correct	1 ms	604 KB	Output is correct

Subtask #3

28.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	604 KB	Output is correct
5	Correct	1 ms	860 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	860 KB	Output is correct
8	Correct	1 ms	860 KB	Output is correct
9	Correct	1 ms	764 KB	Output is correct
10	Correct	1 ms	860 KB	Output is correct
11	Correct	1 ms	604 KB	Output is correct
12	Correct	1 ms	740 KB	Output is correct
13	Correct	1 ms	860 KB	Output is correct
14	Correct	1 ms	736 KB	Output is correct
15	Correct	1 ms	856 KB	Output is correct
16	Correct	1 ms	736 KB	Output is correct
17	Correct	1 ms	604 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	0 ms	348 KB	Output is correct
22	Correct	1 ms	348 KB	Output is correct
23	Correct	1 ms	344 KB	Output is correct
24	Correct	0 ms	348 KB	Output is correct
25	Correct	0 ms	344 KB	Output is correct
26	Correct	1 ms	348 KB	Output is correct
27	Correct	0 ms	348 KB	Output is correct
28	Correct	0 ms	348 KB	Output is correct
29	Correct	0 ms	344 KB	Output is correct
30	Correct	0 ms	344 KB	Output is correct
31	Correct	0 ms	348 KB	Output is correct
32	Correct	0 ms	348 KB	Output is correct
33	Correct	0 ms	348 KB	Output is correct
34	Correct	1 ms	344 KB	Output is correct
35	Correct	1 ms	348 KB	Output is correct
36	Correct	1 ms	344 KB	Output is correct
37	Correct	1 ms	1112 KB	Output is correct
38	Correct	1 ms	604 KB	Output is correct
39	Correct	1 ms	860 KB	Output is correct
40	Correct	1 ms	488 KB	Output is correct
41	Correct	1 ms	348 KB	Output is correct
42	Correct	1 ms	720 KB	Output is correct
43	Correct	1 ms	604 KB	Output is correct

Subtask #4

37.0 / 37.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	1 ms	1112 KB	Output is correct
5	Correct	1 ms	604 KB	Output is correct
6	Correct	1 ms	860 KB	Output is correct
7	Correct	1 ms	488 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	720 KB	Output is correct
10	Correct	1 ms	604 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	1 ms	604 KB	Output is correct
15	Correct	1 ms	860 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	1 ms	860 KB	Output is correct
18	Correct	1 ms	860 KB	Output is correct
19	Correct	1 ms	764 KB	Output is correct
20	Correct	1 ms	860 KB	Output is correct
21	Correct	1 ms	604 KB	Output is correct
22	Correct	1 ms	740 KB	Output is correct
23	Correct	1 ms	860 KB	Output is correct
24	Correct	1 ms	736 KB	Output is correct
25	Correct	1 ms	856 KB	Output is correct
26	Correct	1 ms	736 KB	Output is correct
27	Correct	1 ms	604 KB	Output is correct
28	Correct	0 ms	348 KB	Output is correct
29	Correct	0 ms	348 KB	Output is correct
30	Correct	0 ms	348 KB	Output is correct
31	Correct	0 ms	348 KB	Output is correct
32	Correct	1 ms	348 KB	Output is correct
33	Correct	1 ms	344 KB	Output is correct
34	Correct	0 ms	348 KB	Output is correct
35	Correct	0 ms	344 KB	Output is correct
36	Correct	1 ms	348 KB	Output is correct
37	Correct	0 ms	348 KB	Output is correct
38	Correct	0 ms	348 KB	Output is correct
39	Correct	0 ms	344 KB	Output is correct
40	Correct	0 ms	344 KB	Output is correct
41	Correct	0 ms	348 KB	Output is correct
42	Correct	0 ms	348 KB	Output is correct
43	Correct	0 ms	348 KB	Output is correct
44	Correct	28 ms	13820 KB	Output is correct
45	Correct	16 ms	3828 KB	Output is correct
46	Correct	25 ms	5212 KB	Output is correct
47	Correct	26 ms	5220 KB	Output is correct
48	Correct	33 ms	14076 KB	Output is correct
49	Correct	32 ms	14848 KB	Output is correct
50	Correct	30 ms	9216 KB	Output is correct
51	Correct	37 ms	15360 KB	Output is correct
52	Correct	32 ms	8204 KB	Output is correct
53	Correct	13 ms	3164 KB	Output is correct
54	Correct	33 ms	13572 KB	Output is correct
55	Correct	32 ms	14900 KB	Output is correct