oj.uz

답안 #143257

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
143257 2019-08-13T12:35:22 Z Benq Sky Walking (IOI19_walk) C++14
100 / 100
 2337 ms 463776 KB 
// yamisobadlol

#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 all(x) begin(x), end(x)
#define rsz resize

const int MOD = 1000000007; // 998244353
const ll INF = 1e18;
const int MX = 200005;
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; for (const auto& a: x) pr(!fst?", ":"",a), fst = 0; // const needed for vector<bool>
        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> void ps(const Arg& first) { 
        pr(first); ps(); // no space at end of line
    }
    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; }
    modular(const ll& 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 void pr(const modular& a) { pr(a.val); }
    friend void re(modular& a) { ll x; re(x); a = modular(x); }
   
    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); }
    friend bool operator<(const modular& a, const modular& b) { return a.val < b.val; }

    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 pow(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) { 
        auto i = invGeneral(a.val,MOD); assert(i != -1);
        return i;
    } // equivalent to return exp(b,MOD-2) if MOD is 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;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template<class T> using pqg = priority_queue<T,vector<T>,greater<T>>;

template<class T> T poll(pqg<T>& x) {
    T y = x.top(); x.pop();
    return y;
}

int nex;

template<int SZ> struct Dijkstra {
    ll dist[SZ];
    vpi adj[SZ];

    void addEdge(int A, int B, int C) {
        adj[A].pb({B,C}); adj[B].pb({A,C}); assert(C >= 0);
        // if undirected
    }

    void init(int st) {
        fill_n(dist,SZ,INF);
        pqg<pl> q; q.push({dist[st] = 0,st});
    	while (sz(q)) {
    		auto x = poll(q); if (dist[x.s] < x.f) continue;
    		trav(y,adj[x.s]) if (x.f+y.s < dist[y.f])
    			q.push({dist[y.f] = x.f+y.s,y.f});
    	}
    }
};

Dijkstra<10000000> D;

int N, M, S, G;
vi X,H;
vector<pair<int,vi>> bridge;
vi xx;

void split(int h, vi& z, set<int>& cur, int x) {
	vi Z;
	F0R(i,sz(z)-1) {
		Z.pb(z[i]);
		if (z[i] < x && x < z[i+1]) {
			// ps("HUH",x,H[x],h);
			if (H[x] >= h) Z.pb(x);
			else {
				auto it = cur.lb(x); assert(*it != x);
				if (z[i] < *prev(it)) Z.pb(*prev(it));
				if (*it < z[i+1]) Z.pb(*it);
			}
		}
	}
	Z.pb(z.back());
	swap(z,Z);
}

vpi cor[500000];
map<int,pi> mm;
vector<pair<int,pi>> BRIDGE;

int makeVert(int seg, int x) {
	cor[seg].pb({x,nex++});
	return nex-1;
}

void tri(int seg, int label, int x) {
	auto it = mm.ub(x); if (it == begin(mm) || prev(it)->s.f < x) return;
	int SEG = prev(it)->s.s; if (BRIDGE[SEG].f > H[x]) return;
	int LABEL = makeVert(SEG,x);
	// ps("HUH",seg,label,x,SEG,LABEL);
	D.addEdge(label,LABEL,abs(BRIDGE[seg].f-BRIDGE[SEG].f));
}

void ins(int seg) {
	int l = BRIDGE[seg].s.f, r = BRIDGE[seg].s.s;
	while (1) {
		auto it = mm.lb(l);
		if (it != begin(mm) && prev(it)->s.f >= l) it --;
		if (it == end(mm) || it->f > r) break;
		auto IT = *it; mm.erase(it);
		if (IT.f < l) mm[IT.f] = {l-1,IT.s.s};
		if (IT.s.f > r) mm[r+1] = {IT.s.f,IT.s.s};
	}
	mm[l] = {r,seg};
}

ll min_distance(vi x, vi h, vi l, vi r, vi y, int s, int g) {
	N = sz(x), M = sz(l); if (s > g) swap(s,g);
	X = x, H = h, S = s, G = g;
	F0R(i,sz(l)) bridge.pb({y[i],{l[i],r[i]}});
	sort(bridge.rbegin(),bridge.rend());
	F0R(i,N) xx.pb(i);
	sort(all(xx),[](int a, int b) { return H[a] > H[b]; });
	int ind = 0; set<int> cur;
	/*trav(z,bridge) ps(z);
	ps();
	trav(t,xx) ps("HUH",t,H[t]);*/

	trav(z,bridge) {
		while (ind < sz(xx) && H[xx[ind]] >= z.f) cur.insert(xx[ind++]);
		// ps("??",z.f,cur);
		split(z.f,z.s,cur,S);
		split(z.f,z.s,cur,G);
	}
	trav(z,bridge) F0R(i,sz(z.s)-1) BRIDGE.pb({z.f,{z.s[i],z.s[i+1]}});
	BRIDGE.pb({0,{S,S}}); BRIDGE.pb({0,{G,G}});
	vi special;
	F0R(i,sz(BRIDGE)) {
		cor[i] = {{BRIDGE[i].s.f,2*i},{BRIDGE[i].s.s,2*i+1}};
		if (BRIDGE[i].f == 0) special.pb(2*i);
	}
	nex = 2*sz(BRIDGE);
	F0R(i,sz(BRIDGE)) {
		// ps("HUH",i,BRIDGE[i]);
		tri(i,2*i,BRIDGE[i].s.f);
		tri(i,2*i+1,BRIDGE[i].s.s);
		ins(i);
	}
	mm.clear();
	F0Rd(i,sz(BRIDGE)) {
		tri(i,2*i,BRIDGE[i].s.f);
		tri(i,2*i+1,BRIDGE[i].s.s);
		ins(i);
	}
	// add bridge edges
	F0R(i,sz(BRIDGE)) {
		sort(all(cor[i]));
		F0R(j,sz(cor[i])-1) D.addEdge(cor[i][j].s,cor[i][j+1].s,X[cor[i][j+1].f]-X[cor[i][j].f]);
	}
	D.init(special[0]);
	auto res = D.dist[special[1]]; if (res == INF) res = -1;
	return res;
	// at most M*5 bridges now
	// for each endpoint of every bridge: add to next thing above it or below it
}

/*int main() {
    setIO();
    ps(min_distance({0,3,5,7,10,12,14},
    				{8,7,9,7,6,6,9},
    				{0,0,0,2,2,3,4},
    				{1,2,6,3,6,4,6},
    				{1,6,8,1,7,2,5},
    				1,5));
    ps(min_distance({0,4,5,6,9},
                    {6,6,6,6,6},
                    {3,1,0},
                    {4,3,2},
                    {1,3,6},
                    0,4));
}*/

Compilation message

walk.cpp: In function 'void io::setIn(std::__cxx11::string)':
walk.cpp:115: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); }
                            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
walk.cpp: In function 'void io::setOut(std::__cxx11::string)':
walk.cpp:116: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
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 315 ms 325188 KB Output is correct
2 Correct 308 ms 325208 KB Output is correct
3 Correct 302 ms 325240 KB Output is correct
4 Correct 307 ms 325356 KB Output is correct
5 Correct 307 ms 325240 KB Output is correct
6 Correct 306 ms 325240 KB Output is correct
7 Correct 305 ms 325240 KB Output is correct
8 Correct 308 ms 325280 KB Output is correct
9 Correct 303 ms 325240 KB Output is correct
10 Correct 306 ms 325324 KB Output is correct
11 Correct 312 ms 325240 KB Output is correct
12 Correct 307 ms 325180 KB Output is correct
13 Correct 307 ms 325228 KB Output is correct
14 Correct 305 ms 325240 KB Output is correct
15 Correct 305 ms 325252 KB Output is correct
16 Correct 308 ms 325240 KB Output is correct
17 Correct 306 ms 325240 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 303 ms 325112 KB Output is correct
2 Correct 307 ms 325192 KB Output is correct
3 Correct 1237 ms 375572 KB Output is correct
4 Correct 1445 ms 379360 KB Output is correct
5 Correct 1000 ms 366828 KB Output is correct
6 Correct 969 ms 365920 KB Output is correct
7 Correct 980 ms 367332 KB Output is correct
8 Correct 1375 ms 375800 KB Output is correct
9 Correct 1542 ms 377056 KB Output is correct
10 Correct 1471 ms 379976 KB Output is correct
11 Correct 1327 ms 374752 KB Output is correct
12 Correct 1253 ms 370400 KB Output is correct
13 Correct 1476 ms 380008 KB Output is correct
14 Correct 872 ms 362924 KB Output is correct
15 Correct 931 ms 366424 KB Output is correct
16 Correct 774 ms 369144 KB Output is correct
17 Correct 859 ms 366312 KB Output is correct
18 Correct 684 ms 380768 KB Output is correct
19 Correct 321 ms 327396 KB Output is correct
20 Correct 495 ms 344936 KB Output is correct
21 Correct 806 ms 370856 KB Output is correct
22 Correct 884 ms 365156 KB Output is correct
23 Correct 818 ms 370656 KB Output is correct
24 Correct 746 ms 367816 KB Output is correct
25 Correct 874 ms 369248 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 572 ms 349144 KB Output is correct
2 Correct 1034 ms 373840 KB Output is correct
3 Correct 1064 ms 374340 KB Output is correct
4 Correct 1151 ms 381016 KB Output is correct
5 Correct 1158 ms 384224 KB Output is correct
6 Correct 1109 ms 382028 KB Output is correct
7 Correct 775 ms 357720 KB Output is correct
8 Correct 1213 ms 370240 KB Output is correct
9 Correct 1078 ms 382944 KB Output is correct
10 Correct 861 ms 382688 KB Output is correct
11 Correct 335 ms 328948 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 572 ms 349144 KB Output is correct
2 Correct 1034 ms 373840 KB Output is correct
3 Correct 1064 ms 374340 KB Output is correct
4 Correct 1151 ms 381016 KB Output is correct
5 Correct 1158 ms 384224 KB Output is correct
6 Correct 1109 ms 382028 KB Output is correct
7 Correct 775 ms 357720 KB Output is correct
8 Correct 1213 ms 370240 KB Output is correct
9 Correct 1078 ms 382944 KB Output is correct
10 Correct 861 ms 382688 KB Output is correct
11 Correct 335 ms 328948 KB Output is correct
12 Correct 1078 ms 374336 KB Output is correct
13 Correct 967 ms 380948 KB Output is correct
14 Correct 1241 ms 384424 KB Output is correct
15 Correct 941 ms 375860 KB Output is correct
16 Correct 1067 ms 379104 KB Output is correct
17 Correct 1092 ms 380768 KB Output is correct
18 Correct 949 ms 375728 KB Output is correct
19 Correct 1067 ms 379196 KB Output is correct
20 Correct 785 ms 356944 KB Output is correct
21 Correct 414 ms 333152 KB Output is correct
22 Correct 882 ms 372832 KB Output is correct
23 Correct 960 ms 374172 KB Output is correct
24 Correct 958 ms 369636 KB Output is correct
25 Correct 979 ms 371680 KB Output is correct
26 Correct 845 ms 362896 KB Output is correct
27 Correct 1192 ms 384268 KB Output is correct
28 Correct 1087 ms 382252 KB Output is correct
29 Correct 1170 ms 382176 KB Output is correct
30 Correct 809 ms 357480 KB Output is correct
31 Correct 1129 ms 382684 KB Output is correct
32 Correct 788 ms 376004 KB Output is correct
33 Correct 813 ms 373888 KB Output is correct
34 Correct 851 ms 375988 KB Output is correct
35 Correct 805 ms 372460 KB Output is correct
36 Correct 988 ms 371936 KB Output is correct
37 Correct 774 ms 370912 KB Output is correct
38 Correct 886 ms 365372 KB Output is correct
39 Correct 864 ms 370452 KB Output is correct
40 Correct 751 ms 367844 KB Output is correct
41 Correct 1045 ms 369480 KB Output is correct

Subtask #5
43.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 315 ms 325188 KB Output is correct
2 Correct 308 ms 325208 KB Output is correct
3 Correct 302 ms 325240 KB Output is correct
4 Correct 307 ms 325356 KB Output is correct
5 Correct 307 ms 325240 KB Output is correct
6 Correct 306 ms 325240 KB Output is correct
7 Correct 305 ms 325240 KB Output is correct
8 Correct 308 ms 325280 KB Output is correct
9 Correct 303 ms 325240 KB Output is correct
10 Correct 306 ms 325324 KB Output is correct
11 Correct 312 ms 325240 KB Output is correct
12 Correct 307 ms 325180 KB Output is correct
13 Correct 307 ms 325228 KB Output is correct
14 Correct 305 ms 325240 KB Output is correct
15 Correct 305 ms 325252 KB Output is correct
16 Correct 308 ms 325240 KB Output is correct
17 Correct 306 ms 325240 KB Output is correct
18 Correct 303 ms 325112 KB Output is correct
19 Correct 307 ms 325192 KB Output is correct
20 Correct 1237 ms 375572 KB Output is correct
21 Correct 1445 ms 379360 KB Output is correct
22 Correct 1000 ms 366828 KB Output is correct
23 Correct 969 ms 365920 KB Output is correct
24 Correct 980 ms 367332 KB Output is correct
25 Correct 1375 ms 375800 KB Output is correct
26 Correct 1542 ms 377056 KB Output is correct
27 Correct 1471 ms 379976 KB Output is correct
28 Correct 1327 ms 374752 KB Output is correct
29 Correct 1253 ms 370400 KB Output is correct
30 Correct 1476 ms 380008 KB Output is correct
31 Correct 872 ms 362924 KB Output is correct
32 Correct 931 ms 366424 KB Output is correct
33 Correct 774 ms 369144 KB Output is correct
34 Correct 859 ms 366312 KB Output is correct
35 Correct 684 ms 380768 KB Output is correct
36 Correct 321 ms 327396 KB Output is correct
37 Correct 495 ms 344936 KB Output is correct
38 Correct 806 ms 370856 KB Output is correct
39 Correct 884 ms 365156 KB Output is correct
40 Correct 818 ms 370656 KB Output is correct
41 Correct 746 ms 367816 KB Output is correct
42 Correct 874 ms 369248 KB Output is correct
43 Correct 572 ms 349144 KB Output is correct
44 Correct 1034 ms 373840 KB Output is correct
45 Correct 1064 ms 374340 KB Output is correct
46 Correct 1151 ms 381016 KB Output is correct
47 Correct 1158 ms 384224 KB Output is correct
48 Correct 1109 ms 382028 KB Output is correct
49 Correct 775 ms 357720 KB Output is correct
50 Correct 1213 ms 370240 KB Output is correct
51 Correct 1078 ms 382944 KB Output is correct
52 Correct 861 ms 382688 KB Output is correct
53 Correct 335 ms 328948 KB Output is correct
54 Correct 1078 ms 374336 KB Output is correct
55 Correct 967 ms 380948 KB Output is correct
56 Correct 1241 ms 384424 KB Output is correct
57 Correct 941 ms 375860 KB Output is correct
58 Correct 1067 ms 379104 KB Output is correct
59 Correct 1092 ms 380768 KB Output is correct
60 Correct 949 ms 375728 KB Output is correct
61 Correct 1067 ms 379196 KB Output is correct
62 Correct 785 ms 356944 KB Output is correct
63 Correct 414 ms 333152 KB Output is correct
64 Correct 882 ms 372832 KB Output is correct
65 Correct 960 ms 374172 KB Output is correct
66 Correct 958 ms 369636 KB Output is correct
67 Correct 979 ms 371680 KB Output is correct
68 Correct 845 ms 362896 KB Output is correct
69 Correct 1192 ms 384268 KB Output is correct
70 Correct 1087 ms 382252 KB Output is correct
71 Correct 1170 ms 382176 KB Output is correct
72 Correct 809 ms 357480 KB Output is correct
73 Correct 1129 ms 382684 KB Output is correct
74 Correct 788 ms 376004 KB Output is correct
75 Correct 813 ms 373888 KB Output is correct
76 Correct 851 ms 375988 KB Output is correct
77 Correct 805 ms 372460 KB Output is correct
78 Correct 988 ms 371936 KB Output is correct
79 Correct 774 ms 370912 KB Output is correct
80 Correct 886 ms 365372 KB Output is correct
81 Correct 864 ms 370452 KB Output is correct
82 Correct 751 ms 367844 KB Output is correct
83 Correct 1045 ms 369480 KB Output is correct
84 Correct 522 ms 343776 KB Output is correct
85 Correct 1200 ms 380072 KB Output is correct
86 Correct 1673 ms 417792 KB Output is correct
87 Correct 404 ms 337012 KB Output is correct
88 Correct 453 ms 337648 KB Output is correct
89 Correct 405 ms 337000 KB Output is correct
90 Correct 362 ms 330356 KB Output is correct
91 Correct 310 ms 325468 KB Output is correct
92 Correct 336 ms 327736 KB Output is correct
93 Correct 723 ms 350312 KB Output is correct
94 Correct 435 ms 333680 KB Output is correct
95 Correct 957 ms 374756 KB Output is correct
96 Correct 984 ms 374428 KB Output is correct
97 Correct 970 ms 369620 KB Output is correct
98 Correct 1000 ms 371760 KB Output is correct
99 Correct 2337 ms 463776 KB Output is correct
100 Correct 1270 ms 382612 KB Output is correct
101 Correct 1695 ms 410228 KB Output is correct
102 Correct 837 ms 357792 KB Output is correct
103 Correct 817 ms 375792 KB Output is correct
104 Correct 816 ms 373828 KB Output is correct
105 Correct 853 ms 375944 KB Output is correct
106 Correct 839 ms 374112 KB Output is correct
107 Correct 822 ms 368224 KB Output is correct
108 Correct 358 ms 329720 KB Output is correct
109 Correct 1018 ms 371552 KB Output is correct
110 Correct 1040 ms 382432 KB Output is correct
111 Correct 1006 ms 383712 KB Output is correct
112 Correct 857 ms 373580 KB Output is correct
113 Correct 952 ms 371424 KB Output is correct