답안 #285459

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
285459	2020-08-29T04:22:51 Z	user202729	Sky Walking (IOI19_walk)	C++17	100 / 100	1312 ms	67384 KB

walk

// moreflags=grader.cpp

// aren't the test cases for subtask 1 not strong enough?

// 14

#ifndef LOCAL
#define NDEBUG 1
#endif
//#include<bits/stdc++.h>
#include<vector>
#include<set>
#include<map>
#include<cstdint>
#include<cassert>
#include<algorithm>
#include<climits>

#include "walk.h"

struct Value{
	std::set<int> have; //{y}
	std::map<int, int64_t> value;
	std::set<int> unstable;

	Value(){
		have.insert(0);
		value[0]=0;
	}

	void smoothen(int const curHeight){
		while(not unstable.empty()){ // smoothen part <= curHeight
			auto const pos=*unstable.begin();
			if(pos>curHeight) break;

			unstable.erase(unstable.begin());
			auto const iterator=value.find(pos);
			while(iterator!=value.begin()){
				auto const prev=std::prev(iterator);
				if(prev->second > iterator->second+iterator->first-prev->first)
					value.erase(prev);
				else
					break;
			}
		}

		if(auto const iterator=value.upper_bound(curHeight);
				iterator!=value.end()) unstable.insert(iterator->first);
	}

	void addOpen(int y, int curHeight){
		auto const [haveIterator, haveInserted]=have.insert(y);
		assert(haveInserted);

		auto const [iterator, inserted]=value.insert({y, 0});
		assert(inserted);
		int64_t curValue=INT64_MAX/2;
		if(iterator!=value.begin()){
			auto [y_, value1]=*std::prev(iterator);
			assert(y_<y);
			curValue=y-y_+value1;
		}
		if(std::next(iterator)!=value.end()){
			auto [y_, value1]=*std::next(iterator);
			//if(y_<=curHeight)
			if(*std::next(haveIterator)<=curHeight)
				curValue=std::min(curValue, y_-y+value1);
		}
		iterator->second=curValue;
	}

	void addClose(int y){
		auto const curHave=have.erase(have.find(y));
		auto curValue=value.find(y);
		if(curValue!=value.end()){
			auto const curValue_=curValue->second;
			auto const nextValue=value.erase(curValue);
			if(curHave!=have.begin()){
				auto const prevHave=std::prev(curHave);
				auto const newValue_=curValue_+y-*prevHave;

				auto const newValueIterator=value.insert(nextValue, {*prevHave, newValue_});
				// do nothing if *prevHave already exists in value
			}
		}
		assert(not unstable.count(y));
	}

	int64_t get(int pos)const{
		assert(have.count(pos));
		auto const [pos_, value_]=*value.lower_bound(pos);
		return value_+pos_-pos;
	}

	int64_t getLoose(int pos, int curHeight){
		// terrible and slow implementation...?
		assert(pos<=curHeight);
		bool const add=not have.count(pos);
		if(add) addOpen(pos, curHeight);
		auto const result=get(pos);
		if(add) addClose(pos);
		return result;
	}

	static void minimize(int y, std::array<Value, 2>& value, std::array<int, 2> const offset){
		// also kinda terrible and slow implementation
		std::array<bool, 2> add{};
		std::array<int64_t, 2> value_;
		for(int index=0; index<2; ++index){
			if(not value[index].have.count(y)){
				value[index].addOpen(y, y);
				add[index]=true;
			}

			value_[index]=value[index].get(y);
		}
		for(int index=0; index<2; ++index){
			if(auto const value1=2*offset[not index]+value_[not index]; value1<value_[index]){
				auto& cur=value[index];
				cur.value[y]=value1;
				assert(cur.unstable.empty() or *cur.unstable.begin()>y);
				cur.unstable.insert(cur.unstable.begin(), y);
				assert(*cur.unstable.begin()==y);
				cur.smoothen(y);
				assert(cur.unstable.empty() or *cur.unstable.begin()>y);
			}
		}
		for(int index=0; index<2; ++index){
			if(add[index])
				value[index].addClose(y);
		}
	}
};

long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r,
		std::vector<int> y, int s, int g) {
	if(s>g) std::swap(s, g);

	struct Segment{ int left, right; };

	std::array<std::map<int, std::vector<Segment>>, 3> parts;
	std::array<std::vector<std::pair<int, Segment>>, 2> tops;
	auto const splitSegments=[&](bool keepParts){ // split segments into parts and tops
		std::map<int, std::vector<Segment>> segments;
		for(int index=0; index<(int)y.size(); ++index)
			segments[y[index]].push_back({l[index], r[index]});

		for(auto& it: tops) it.clear();
		for(auto& it: parts) it.clear();


		std::set<int> remaining;
		std::vector<std::pair<int, int>> heights(x.size());
		for(int it=0; it<(int)x.size(); ++it){
			remaining.insert(remaining.end(), it);
			heights[it]={h[it], it};
		}
		std::sort(begin(heights), end(heights),[&](auto first, auto sec){return first.first>sec.first;});

		for(auto& [y, it]: segments){
			while(not heights.empty() and heights.back().first<y){
				remaining.erase(remaining.find(heights.back().second));
				heights.pop_back();
			}

			assert(not it.empty());
			std::sort(begin(it), end(it),[&](auto first, auto sec){return first.left<sec.left;});
			auto out=++it.begin();
			std::for_each(out, it.end(),[&](auto segment){
				assert(out[-1].right<=segment.left);
				assert(segment.left<segment.right);
				if(out[-1].right==segment.left)
					out[-1].right=segment.right;
				else
					*out++=segment;
			});
			it.erase(out, it.end());

			for(auto [left, right]: it){
				assert(remaining.count(left));
				assert(remaining.count(right));
				assert(left<right);

				for(int i=0; i<2; ++i){
					if(left==right) break;
					auto const cut=i==0 ? s: g;
					if(i==1) assert(left>=s);
					if(left<right and left<cut){
						auto iterator=remaining.upper_bound(cut);
						auto const right1=right<=cut ? right: *std::prev(iterator);
						assert(left<=right1);
						if(left<right1){
							if(keepParts)
								parts[i][y].push_back({left, right1});
							left=right1;
						}

						if(left<right and left<cut){
							if(i==1){
								assert(left>=s); assert(*iterator>g);
							}
							tops[i].push_back({y, {left, *iterator}});
							left=*iterator;
							assert(left<=right);
						}
					}
				}

				assert(left<=right);
				if(left<right){
					assert(left>=g);
					if(keepParts)
						parts[2][y].push_back({left, right});
					left=right;
				}
			}
		}

		for(auto& it: tops) assert(std::is_sorted(begin(it), end(it),
					[&](auto first, auto sec){return first.first<sec.first;}));
	};
	splitSegments(false);


	{ // remap so that each top endpoint has a distinct x index
		std::vector<std::vector<int>> addLeft(x.size()), addRight(x.size());
		for(auto const& it: tops)
			for(auto [y, leftRight]: it){
				addRight[leftRight.left].push_back(y);
				addLeft[leftRight.right].push_back(y);
			}

		std::vector<int> map(x.size());
		std::vector<int> newx, newHeight;

		for(int index=0; index<(int)x.size(); ++index){
			std::sort(begin(addLeft[index]), end(addLeft[index]));
			std::sort(begin(addRight[index]), end(addRight[index]), std::greater<>());
			auto const curx=x[index], curHeight=h[index];
			for(auto height: addLeft[index]){
				assert(height<=curHeight);
				newx.push_back(curx); newHeight.push_back(height);
			}
			map[index]=(int)newx.size();
			newx.push_back(curx); newHeight.push_back(curHeight);
			for(auto height: addRight[index]){
				assert(height<=curHeight);
				newx.push_back(curx); newHeight.push_back(height);
			}
		}

		x=std::move(newx);
		h=std::move(newHeight);
		s=map[s]; g=map[g];
		for(auto& it: l) it=map[it];
		for(auto& it: r) it=map[it];
	}

	splitSegments(true);
	y.clear(); l.clear(); r.clear();

	struct Query{int pos, y;};
	std::vector<Query> queries;
	std::vector<int> distances;
	for(auto const& it: tops)
		for(auto [y, leftRight]: it){
			queries.push_back({leftRight.left, y});
			queries.push_back({leftRight.right, y});
			distances.push_back(x[leftRight.right]-x[leftRight.left]);
		}
	queries.push_back({s, 0});
	queries.push_back({g, 0});
	for(auto [pos, y]: queries) assert(y<=h[pos]);
	std::vector<std::array<int64_t, 2>> queryResult(queries.size(), {INT64_MAX/2, INT64_MAX/2});

	tops[0].push_back({INT_MAX, {0, (int)x.size()-1}});

	for(auto [y, leftRight]: tops[0])
		if(leftRight.right>g){
			assert(leftRight.left<s);
			tops[1].push_back({y, leftRight});
		}


	enum class Type{ open, query, close };
	struct Event{ int y, index; Type type; int queryIndex; };
	for(int index0=0; index0<2; ++index0){
		std::array<std::vector<Event>, 2> events;
		auto const start=index0==0 ? s: g;

		for(int queryIndex=0; queryIndex<(int)queries.size(); ++queryIndex){
			auto const [pos, y]=queries[queryIndex];
			if(pos<start) events[0].push_back({y, pos, Type::query, queryIndex});
			else if(pos>start) events[1].push_back({y, pos, Type::query, queryIndex});
			else queryResult[queryIndex][index0]=y;
		}

		for(auto const& [y, it]: parts[1+index0]){
			for(auto const it: it){
				assert(it.left>=start);
				events[1].push_back({y, it.left, Type::open});
				events[1].push_back({y, it.right, Type::close});
			}
		}
		events[1].push_back({0, start, Type::close});
		//events[1].push_back({0, g, Types::open});
		std::sort(begin(events[1]), end(events[1]),[&](Event first, Event sec){
			return first.index!=sec.index ? first.index>sec.index: first.type>sec.type;
			// reverse(increasing index->increasing type)
		});


		for(auto const& [y, it]: parts[0+index0]){
			for(auto const it: it){
				assert(it.right<=start);
				events[0].push_back({y, it.right, Type::open});
				events[0].push_back({y, it.left, Type::close});
			}
		}
		events[0].push_back({0, start, Type::close});
		//events[0].push_back({0, 0, Type::open});
		std::sort(begin(events[0]), end(events[0]),[&](Event first, Event sec){
			return first.index!=sec.index ? first.index<sec.index: first.type>sec.type;
			// reverse(decreasing index->increasing type)
		});

		auto const process1=[&](Value& value, int const index, std::vector<Event>& events){ // Type::open
			auto const curHeight=h[index];
			value.smoothen(curHeight);

			while(not events.empty() and events.back().index==index){
				auto const [y, index_, type, _]=events.back();
				assert(index==index_);
				assert(y<=curHeight);
				if(type==Type::open){
					value.addOpen(y, curHeight);
				}else{
					return;
				}
				events.pop_back();
			}
		};

		auto const process2=[&](Value& value, int const index, std::vector<Event>& events, int const offset){ // Type::{query, close}
			auto const curHeight=h[index];
			while(not events.empty() and events.back().index==index){
				auto const [y, index_, type, queryIndex]=events.back();
				assert(index==index_);
				assert(y<=curHeight);
				if(type==Type::close){
					value.addClose(y);
				}else{
					assert(type==Type::query);
					queryResult[queryIndex][index0]=value.getLoose(y, curHeight)+offset;
				}
				events.pop_back();
			}
		};

		std::array<int, 2> bounds{{start, start}};
		std::array<Value, 2> value;
		process1(value[0], start, events[0]);
		process1(value[1], start, events[1]);
		process2(value[0], start, events[0], 0);
		process2(value[1], start, events[1], 0);

		for(auto const [y, leftRight]: tops[index0]){
			auto const [left, right]=leftRight;

			assert(bounds[0]>=left);
			while(bounds[0]>left){
				process1(value[0], --bounds[0], events[0]);
				if(bounds[0]>left)
					process2(value[0], bounds[0], events[0], x[start]-x[bounds[0]]);
			}
			assert(bounds[1]<=right);
			while(bounds[1]<right){
				process1(value[1], ++bounds[1], events[1]);
				if(bounds[1]<right)
					process2(value[1], bounds[1], events[1], x[bounds[1]]-x[start]);
			}

			std::array<int, 2> const offset{{x[start]-x[left], x[right]-x[start]}};
			Value::minimize(y, value, offset);
			process2(value[0], bounds[0], events[0], offset[0]);
			process2(value[1], bounds[1], events[1], offset[1]);
		}
	}

	int64_t result=INT64_MAX;
	for(auto [a, b]: queryResult){
		if(a<INT64_MAX/2 and b<INT64_MAX/2)
			result=std::min(result, a+b);
	}
	for(int index=0; index<(int)distances.size(); ++index){
		auto const [a, b]=queryResult[index*2];
		auto const [c, d]=queryResult[index*2+1];
		if(a<INT64_MAX/2 and d<INT64_MAX/2)
			result=std::min(result, a+d+distances[index]);
		if(b<INT64_MAX/2 and c<INT64_MAX/2)
			result=std::min(result, b+c+distances[index]);
	}
	return result==INT64_MAX ? -1: result;
}

Compilation message

walk.cpp: In member function 'void Value::addClose(int)':
walk.cpp:82:16: warning: variable 'newValueIterator' set but not used [-Wunused-but-set-variable]
   82 |     auto const newValueIterator=value.insert(nextValue, {*prevHave, newValue_});
      |                ^~~~~~~~~~~~~~~~
walk.cpp: In lambda function:
walk.cpp:219:13: warning: unused variable 'it' [-Wunused-variable]
  219 |   for(auto& it: tops) assert(std::is_sorted(begin(it), end(it),
      |             ^~
walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:273:11: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
  273 |  for(auto [pos, y]: queries) assert(y<=h[pos]);
      |           ^~~~~~~~

Subtask #1

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	256 KB	Output is correct
2	Correct	0 ms	256 KB	Output is correct
3	Correct	0 ms	256 KB	Output is correct
4	Correct	0 ms	256 KB	Output is correct
5	Correct	1 ms	256 KB	Output is correct
6	Correct	0 ms	256 KB	Output is correct
7	Correct	1 ms	256 KB	Output is correct
8	Correct	1 ms	256 KB	Output is correct
9	Correct	0 ms	256 KB	Output is correct
10	Correct	1 ms	256 KB	Output is correct
11	Correct	0 ms	256 KB	Output is correct
12	Correct	1 ms	256 KB	Output is correct
13	Correct	1 ms	256 KB	Output is correct
14	Correct	1 ms	384 KB	Output is correct
15	Correct	1 ms	256 KB	Output is correct
16	Correct	0 ms	256 KB	Output is correct
17	Correct	1 ms	256 KB	Output is correct

Subtask #2

14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	256 KB	Output is correct
2	Correct	0 ms	256 KB	Output is correct
3	Correct	387 ms	25140 KB	Output is correct
4	Correct	587 ms	30052 KB	Output is correct
5	Correct	334 ms	24920 KB	Output is correct
6	Correct	375 ms	26708 KB	Output is correct
7	Correct	345 ms	22792 KB	Output is correct
8	Correct	391 ms	25128 KB	Output is correct
9	Correct	564 ms	28760 KB	Output is correct
10	Correct	631 ms	29524 KB	Output is correct
11	Correct	435 ms	26620 KB	Output is correct
12	Correct	563 ms	29800 KB	Output is correct
13	Correct	593 ms	29888 KB	Output is correct
14	Correct	536 ms	36492 KB	Output is correct
15	Correct	402 ms	27708 KB	Output is correct
16	Correct	248 ms	17944 KB	Output is correct
17	Correct	227 ms	16440 KB	Output is correct
18	Correct	492 ms	33004 KB	Output is correct
19	Correct	23 ms	3112 KB	Output is correct
20	Correct	269 ms	29560 KB	Output is correct
21	Correct	187 ms	16128 KB	Output is correct
22	Correct	233 ms	18360 KB	Output is correct
23	Correct	428 ms	23628 KB	Output is correct
24	Correct	233 ms	18172 KB	Output is correct
25	Correct	214 ms	16416 KB	Output is correct

Subtask #3

15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	32 ms	2560 KB	Output is correct
2	Correct	419 ms	24596 KB	Output is correct
3	Correct	458 ms	25268 KB	Output is correct
4	Correct	514 ms	31716 KB	Output is correct
5	Correct	612 ms	31844 KB	Output is correct
6	Correct	557 ms	31852 KB	Output is correct
7	Correct	269 ms	19816 KB	Output is correct
8	Correct	450 ms	31716 KB	Output is correct
9	Correct	582 ms	31848 KB	Output is correct
10	Correct	321 ms	21948 KB	Output is correct
11	Correct	30 ms	4208 KB	Output is correct

Subtask #4

18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	32 ms	2560 KB	Output is correct
2	Correct	419 ms	24596 KB	Output is correct
3	Correct	458 ms	25268 KB	Output is correct
4	Correct	514 ms	31716 KB	Output is correct
5	Correct	612 ms	31844 KB	Output is correct
6	Correct	557 ms	31852 KB	Output is correct
7	Correct	269 ms	19816 KB	Output is correct
8	Correct	450 ms	31716 KB	Output is correct
9	Correct	582 ms	31848 KB	Output is correct
10	Correct	321 ms	21948 KB	Output is correct
11	Correct	30 ms	4208 KB	Output is correct
12	Correct	473 ms	25152 KB	Output is correct
13	Correct	751 ms	29796 KB	Output is correct
14	Correct	833 ms	31588 KB	Output is correct
15	Correct	297 ms	19148 KB	Output is correct
16	Correct	442 ms	23952 KB	Output is correct
17	Correct	445 ms	21964 KB	Output is correct
18	Correct	300 ms	19280 KB	Output is correct
19	Correct	449 ms	23940 KB	Output is correct
20	Correct	418 ms	18244 KB	Output is correct
21	Correct	158 ms	8296 KB	Output is correct
22	Correct	416 ms	22008 KB	Output is correct
23	Correct	414 ms	25148 KB	Output is correct
24	Correct	432 ms	25284 KB	Output is correct
25	Correct	431 ms	26852 KB	Output is correct
26	Correct	475 ms	27692 KB	Output is correct
27	Correct	892 ms	30212 KB	Output is correct
28	Correct	653 ms	29288 KB	Output is correct
29	Correct	815 ms	30052 KB	Output is correct
30	Correct	379 ms	18272 KB	Output is correct
31	Correct	840 ms	29544 KB	Output is correct
32	Correct	235 ms	18776 KB	Output is correct
33	Correct	289 ms	18896 KB	Output is correct
34	Correct	336 ms	20944 KB	Output is correct
35	Correct	311 ms	17908 KB	Output is correct
36	Correct	261 ms	18468 KB	Output is correct
37	Correct	190 ms	13316 KB	Output is correct
38	Correct	233 ms	15288 KB	Output is correct
39	Correct	427 ms	20812 KB	Output is correct
40	Correct	220 ms	15156 KB	Output is correct
41	Correct	195 ms	13732 KB	Output is correct

Subtask #5

43.0 / 43.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	256 KB	Output is correct
2	Correct	0 ms	256 KB	Output is correct
3	Correct	0 ms	256 KB	Output is correct
4	Correct	0 ms	256 KB	Output is correct
5	Correct	1 ms	256 KB	Output is correct
6	Correct	0 ms	256 KB	Output is correct
7	Correct	1 ms	256 KB	Output is correct
8	Correct	1 ms	256 KB	Output is correct
9	Correct	0 ms	256 KB	Output is correct
10	Correct	1 ms	256 KB	Output is correct
11	Correct	0 ms	256 KB	Output is correct
12	Correct	1 ms	256 KB	Output is correct
13	Correct	1 ms	256 KB	Output is correct
14	Correct	1 ms	384 KB	Output is correct
15	Correct	1 ms	256 KB	Output is correct
16	Correct	0 ms	256 KB	Output is correct
17	Correct	1 ms	256 KB	Output is correct
18	Correct	1 ms	256 KB	Output is correct
19	Correct	0 ms	256 KB	Output is correct
20	Correct	387 ms	25140 KB	Output is correct
21	Correct	587 ms	30052 KB	Output is correct
22	Correct	334 ms	24920 KB	Output is correct
23	Correct	375 ms	26708 KB	Output is correct
24	Correct	345 ms	22792 KB	Output is correct
25	Correct	391 ms	25128 KB	Output is correct
26	Correct	564 ms	28760 KB	Output is correct
27	Correct	631 ms	29524 KB	Output is correct
28	Correct	435 ms	26620 KB	Output is correct
29	Correct	563 ms	29800 KB	Output is correct
30	Correct	593 ms	29888 KB	Output is correct
31	Correct	536 ms	36492 KB	Output is correct
32	Correct	402 ms	27708 KB	Output is correct
33	Correct	248 ms	17944 KB	Output is correct
34	Correct	227 ms	16440 KB	Output is correct
35	Correct	492 ms	33004 KB	Output is correct
36	Correct	23 ms	3112 KB	Output is correct
37	Correct	269 ms	29560 KB	Output is correct
38	Correct	187 ms	16128 KB	Output is correct
39	Correct	233 ms	18360 KB	Output is correct
40	Correct	428 ms	23628 KB	Output is correct
41	Correct	233 ms	18172 KB	Output is correct
42	Correct	214 ms	16416 KB	Output is correct
43	Correct	32 ms	2560 KB	Output is correct
44	Correct	419 ms	24596 KB	Output is correct
45	Correct	458 ms	25268 KB	Output is correct
46	Correct	514 ms	31716 KB	Output is correct
47	Correct	612 ms	31844 KB	Output is correct
48	Correct	557 ms	31852 KB	Output is correct
49	Correct	269 ms	19816 KB	Output is correct
50	Correct	450 ms	31716 KB	Output is correct
51	Correct	582 ms	31848 KB	Output is correct
52	Correct	321 ms	21948 KB	Output is correct
53	Correct	30 ms	4208 KB	Output is correct
54	Correct	473 ms	25152 KB	Output is correct
55	Correct	751 ms	29796 KB	Output is correct
56	Correct	833 ms	31588 KB	Output is correct
57	Correct	297 ms	19148 KB	Output is correct
58	Correct	442 ms	23952 KB	Output is correct
59	Correct	445 ms	21964 KB	Output is correct
60	Correct	300 ms	19280 KB	Output is correct
61	Correct	449 ms	23940 KB	Output is correct
62	Correct	418 ms	18244 KB	Output is correct
63	Correct	158 ms	8296 KB	Output is correct
64	Correct	416 ms	22008 KB	Output is correct
65	Correct	414 ms	25148 KB	Output is correct
66	Correct	432 ms	25284 KB	Output is correct
67	Correct	431 ms	26852 KB	Output is correct
68	Correct	475 ms	27692 KB	Output is correct
69	Correct	892 ms	30212 KB	Output is correct
70	Correct	653 ms	29288 KB	Output is correct
71	Correct	815 ms	30052 KB	Output is correct
72	Correct	379 ms	18272 KB	Output is correct
73	Correct	840 ms	29544 KB	Output is correct
74	Correct	235 ms	18776 KB	Output is correct
75	Correct	289 ms	18896 KB	Output is correct
76	Correct	336 ms	20944 KB	Output is correct
77	Correct	311 ms	17908 KB	Output is correct
78	Correct	261 ms	18468 KB	Output is correct
79	Correct	190 ms	13316 KB	Output is correct
80	Correct	233 ms	15288 KB	Output is correct
81	Correct	427 ms	20812 KB	Output is correct
82	Correct	220 ms	15156 KB	Output is correct
83	Correct	195 ms	13732 KB	Output is correct
84	Correct	31 ms	2868 KB	Output is correct
85	Correct	538 ms	28492 KB	Output is correct
86	Correct	1199 ms	55036 KB	Output is correct
87	Correct	81 ms	11040 KB	Output is correct
88	Correct	157 ms	10728 KB	Output is correct
89	Correct	83 ms	10912 KB	Output is correct
90	Correct	17 ms	1692 KB	Output is correct
91	Correct	2 ms	384 KB	Output is correct
92	Correct	24 ms	2080 KB	Output is correct
93	Correct	331 ms	17484 KB	Output is correct
94	Correct	170 ms	10344 KB	Output is correct
95	Correct	384 ms	26968 KB	Output is correct
96	Correct	366 ms	29412 KB	Output is correct
97	Correct	422 ms	33496 KB	Output is correct
98	Correct	380 ms	27988 KB	Output is correct
99	Correct	1312 ms	67384 KB	Output is correct
100	Correct	721 ms	33748 KB	Output is correct
101	Correct	993 ms	42572 KB	Output is correct
102	Correct	421 ms	21588 KB	Output is correct
103	Correct	252 ms	18904 KB	Output is correct
104	Correct	236 ms	18908 KB	Output is correct
105	Correct	317 ms	21536 KB	Output is correct
106	Correct	373 ms	27172 KB	Output is correct
107	Correct	415 ms	25540 KB	Output is correct
108	Correct	47 ms	3492 KB	Output is correct
109	Correct	852 ms	30760 KB	Output is correct
110	Correct	528 ms	33040 KB	Output is correct
111	Correct	567 ms	33316 KB	Output is correct
112	Correct	320 ms	21388 KB	Output is correct
113	Correct	277 ms	18260 KB	Output is correct