oj.uz

Submission #991214

# Submission time Handle Problem Language Result Execution time Memory
991214 2024-06-01T15:09:46 Z model_code Road Service 2 (JOI24_ho_t5) C++17
100 / 100
 933 ms 297300 KB 
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
#pragma warning (disable: 4996)

// ==================================================================================================================================================== その他の関数
// 位置 pos から x 手で移動できる最大位置
int GetMaxPosition(int pos, int x, vector<vector<int>>& par) {
	if (x == -1) return -50000;
	vector<int> dp0(23, -1);
	vector<int> dp1(23, -1);
	dp0[22] = pos;
	for (int i = 21; i >= 0; i--) {
		if ((x / (1 << i)) % 2 == 0) {
			dp0[i] = dp0[i + 1];
			dp1[i] = dp1[i + 1];
			continue;
		}
		if (dp0[i + 1] != -1) dp0[i] = max(dp0[i], par[3 * i + 1][dp0[i + 1]]);
		if (dp1[i + 1] != -1) dp0[i] = max(dp0[i], par[3 * i + 0][dp1[i + 1]]);
		if (dp0[i + 1] != -1) dp1[i] = max(dp1[i], par[3 * i + 2][dp0[i + 1]]);
		if (dp1[i + 1] != -1) dp1[i] = max(dp1[i], par[3 * i + 1][dp1[i + 1]]);
	}
	return dp0[0];
}

// 位置 pos から位置 goal 以上まで行くための最小コスト
int GetMinCost(int pos, int goal, vector<vector<int>>& par) {
	if (pos == -1) return 1000000000;
	if (pos >= goal) return 0;
	int cur1 = pos;
	int cur2 = -1;
	int ans = 0;
	for (int i = 21; i >= 0; i--) {
		int v1 = -1;
		int v2 = -1;
		if (cur1 != -1) v1 = max(v1, par[3 * i + 1][cur1]);
		if (cur2 != -1) v1 = max(v1, par[3 * i + 0][cur2]);
		if (cur1 != -1) v2 = max(v2, par[3 * i + 2][cur1]);
		if (cur2 != -1) v2 = max(v2, par[3 * i + 1][cur2]);
		if (v1 < goal && v2 < goal) {
			cur1 = v1;
			cur2 = v2;
			ans += (1 << i);
		}
	}
	if (cur1 != -1 && par[1][cur1] >= goal) return ans + 1;
	if (cur2 != -1 && par[1][cur2] >= goal) return ans + 2;
	if (cur1 != -1 && par[2][cur1] >= goal) return ans + 2;
	return ans + 3;
}

// 極小な区間だけを取り出す関数
vector<pair<int, int>> OnlyMinimal(vector<pair<int, int>> Ranges) {
	for (int i = 0; i < Ranges.size(); i++) Ranges[i].first *= -1;
	sort(Ranges.begin(), Ranges.end());
	vector<pair<int, int>> Return;
	int MinValue = (1 << 30);
	for (int i = 0; i < Ranges.size(); i++) {
		if (MinValue > Ranges[i].second) {
			MinValue = Ranges[i].second;
			Return.push_back(Ranges[i]);
		}
	}
	for (int i = 0; i < Return.size(); i++) Return[i].first *= -1;
	sort(Return.begin(), Return.end());
	return Return;
}

// 位置 pos を区間 [cl, cr] に修正
pair<int, int> FixPosition(int moto, int pos, int cl, int cr, int cost, vector<int>& C, vector<int>& NextCost1, vector<int>& NextCost2, vector<vector<int>>& par, vector<int>& UpLim) {
	if (pos < cl) return make_pair(-1, 1000000000);
	if (pos <= cr) return make_pair(pos, cost);
	if (C[pos] == 1) {
		int idx1 = NextCost1[cr];
		int idx2 = NextCost2[cr];
		int result = -1;
		if (idx1 >= cl) result = max(result, idx1);
		if (cost >= 2) {
			int prepos = GetMaxPosition(moto, cost - 2, par);
			int nexpos = UpLim[prepos];
			if (nexpos >= cl && NextCost2[min(cr, nexpos)] >= cl) result = max(result, NextCost2[min(cr, nexpos)]);
		}
		if (result != -1) return make_pair(result, cost);
		return make_pair(idx2, cost + 1);
	}
	return make_pair(NextCost2[cr], cost);
}

// 位置 pos から区間 [cl, cr] に行くための最小コスト
int RangeCost(int pos, int cl, int cr, vector<int>& C, vector<int>& NextCost1, vector<int>& NextCost2, vector<vector<int>>& par, vector<int>& UpLim) {
	int base = GetMinCost(pos, cl, par);
	int newpos = GetMaxPosition(pos, base, par);
	pair<int, int> fixpos = FixPosition(pos, newpos, cl, cr, base, C, NextCost1, NextCost2, par, UpLim);
	return fixpos.second;
}

// ==================================================================================================================================================== 問題を解く関数
vector<int> solve_subtask8(int H, int W, int Q, vector<vector<char>> A, vector<vector<char>> B, vector<int> C, vector<vector<pair<int, int>>> Query) {
	// Step 1. 連結成分を探す
	vector<vector<int>> GroupID(H, vector<int>(W, -1));
	int GroupCnt = 0;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			if (GroupID[i][j] != -1) continue;
			queue<pair<int, int>> Que;
			Que.push(make_pair(i, j));
			GroupID[i][j] = GroupCnt;
			while (!Que.empty()) {
				int px = Que.front().first;
				int py = Que.front().second;
				Que.pop();
				if (px - 1 >= 0 && B[px - 1][py] == '1' && GroupID[px - 1][py] == -1) {
					GroupID[px - 1][py] = GroupCnt;
					Que.push(make_pair(px - 1, py));
				}
				if (px + 1 < H && B[px][py] == '1' && GroupID[px + 1][py] == -1) {
					GroupID[px + 1][py] = GroupCnt;
					Que.push(make_pair(px + 1, py));
				}
				if (py - 1 >= 0 && A[px][py - 1] == '1' && GroupID[px][py - 1] == -1) {
					GroupID[px][py - 1] = GroupCnt;
					Que.push(make_pair(px, py - 1));
				}
				if (py + 1 < W && A[px][py] == '1' && GroupID[px][py + 1] == -1) {
					GroupID[px][py + 1] = GroupCnt;
					Que.push(make_pair(px, py + 1));
				}
			}
			GroupCnt += 1;
		}
	}

	// Step 2. 各連結成分に対応する区間を求める
	vector<pair<int, int>> Range(GroupCnt, make_pair(100000000, -100000000));
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			Range[GroupID[i][j]].first = min(Range[GroupID[i][j]].first, i);
			Range[GroupID[i][j]].second = max(Range[GroupID[i][j]].second, i);
		}
	}

	// Step 3. 各地点の直前のコスト 1, 2 の位置を計算
	vector<int> NextCost1(H, -1);
	vector<int> NextCost2(H, -1);
	for (int i = 0; i < H; i++) {
		if (i >= 1) {
			NextCost1[i] = NextCost1[i - 1];
			NextCost2[i] = NextCost2[i - 1];
		}
		if (C[i] == 1) NextCost1[i] = i;
		if (C[i] == 2) NextCost2[i] = i;
	}

	// Step 4. 最大値を計算
	vector<int> UpLim(H, -1);
	for (int i = 0; i < H; i++) UpLim[i] = i;
	for (pair<int, int> idx : Range) {
		UpLim[idx.first] = max(UpLim[idx.first], idx.second);
	}
	for (int i = 1; i < H; i++) UpLim[i] = max(UpLim[i], UpLim[i - 1]);

	// Step 5. ダブリングの初期化
	// par[3*d+e][i] ã¯é ‚ç‚¹ i からコスト 2^d+(e-1) でどこまで行けるか
	vector<vector<int>> par(66, vector<int>(H, -1));
	for (int i = 0; i < H; i++) par[0][i] = i;
	for (int i = 0; i < H; i++) par[1][i] = max(i, NextCost1[UpLim[i]]);
	for (int i = 0; i < H; i++) {
		int v1 = NextCost2[UpLim[i]];
		int v2 = NextCost1[UpLim[i]];
		int v3 = (v2 == -1 ? -1 : NextCost1[UpLim[v2]]);
		par[2][i] = max({ i, v1, v3 });
	}

	// Step 6. ダブリングの計算
	for (int d = 3; d < 66; d += 3) {
		for (int i = 0; i < H; i++) {
			par[d + 0][i] = max({ par[d - 3][par[d - 2][i]], par[d - 2][par[d - 3][i]] });
			par[d + 1][i] = max({ par[d - 3][par[d - 1][i]], par[d - 2][par[d - 2][i]], par[d - 1][par[d - 3][i]] });
			par[d + 2][i] = max({ par[d - 2][par[d - 1][i]], par[d - 1][par[d - 2][i]] });
		}
	}

	// Step 7. 各クエリにおける答えを計算
	vector<int> Answer(Q, -1);
	for (int t = 0; t < Q; t++) {
		vector<int> Groups;
		for (pair<int, int> idx : Query[t]) Groups.push_back(GroupID[idx.first][idx.second]);
		sort(Groups.begin(), Groups.end());
		Groups.erase(unique(Groups.begin(), Groups.end()), Groups.end());
		if (Groups.size() == 1) {
			Answer[t] = 0;
		}
		else {
			vector<pair<int, int>> List;
			for (int idx : Groups) List.push_back(Range[idx]);
			vector<pair<int, int>> Important = OnlyMinimal(List);
			vector<int> dpval(Important.size(), 1000000000);
			vector<int> dp0(Important.size(), -1);
			vector<int> dp1(Important.size(), -1);

			// 初期値の計算
			if (NextCost1[Important[0].second] < Important[0].first) {
				dpval[0] = 2;
				dp0[0] = NextCost2[Important[0].second];
				dp1[0] = -1;
			}
			else {
				dpval[0] = 1;
				dp0[0] = NextCost1[Important[0].second]; if (dp0[0] < Important[0].first) dp0[0] = -1;
				dp1[0] = NextCost2[Important[0].second]; if (dp1[0] < Important[0].first) dp1[0] = -1;
			}

			// 動的計画法
			for (int i = 1; i < Important.size(); i++) {
				int cl = Important[i].first;
				int cr = Important[i].second;
				int cost1 = 1000000000; if (dp0[i - 1] != -1) cost1 = RangeCost(dp0[i - 1], cl, cr, C, NextCost1, NextCost2, par, UpLim);
				int cost2 = 1000000000; if (dp1[i - 1] != -1) cost2 = RangeCost(dp1[i - 1], cl, cr, C, NextCost1, NextCost2, par, UpLim);
				dpval[i] = min({ dpval[i], dpval[i - 1] + cost1, dpval[i - 1] + cost2 + 1 });
				if (dpval[i] > 2 * H) break;
				int pos1 = GetMaxPosition(dp0[i - 1], dpval[i] - (dpval[i - 1] + 0) + 0, par);
				int pos2 = GetMaxPosition(dp1[i - 1], dpval[i] - (dpval[i - 1] + 1) + 0, par);
				int pos3 = GetMaxPosition(dp0[i - 1], dpval[i] - (dpval[i - 1] + 0) + 1, par);
				int pos4 = GetMaxPosition(dp1[i - 1], dpval[i] - (dpval[i - 1] + 1) + 1, par);
				pair<int, int> fix1 = FixPosition(dp0[i - 1], pos1, cl, cr, dpval[i] - (dpval[i - 1] + 0) + 0, C, NextCost1, NextCost2, par, UpLim);
				pair<int, int> fix2 = FixPosition(dp1[i - 1], pos2, cl, cr, dpval[i] - (dpval[i - 1] + 1) + 0, C, NextCost1, NextCost2, par, UpLim);
				pair<int, int> fix3 = FixPosition(dp0[i - 1], pos3, cl, cr, dpval[i] - (dpval[i - 1] + 0) + 1, C, NextCost1, NextCost2, par, UpLim);
				pair<int, int> fix4 = FixPosition(dp1[i - 1], pos4, cl, cr, dpval[i] - (dpval[i - 1] + 1) + 1, C, NextCost1, NextCost2, par, UpLim);
				if (fix1.second + (dpval[i - 1] + 0) == dpval[i] + 0) dp0[i] = max(dp0[i], fix1.first);
				if (fix1.second + (dpval[i - 1] + 0) == dpval[i] + 1) dp1[i] = max(dp1[i], fix1.first);
				if (fix2.second + (dpval[i - 1] + 1) == dpval[i] + 0) dp0[i] = max(dp0[i], fix2.first);
				if (fix2.second + (dpval[i - 1] + 1) == dpval[i] + 1) dp1[i] = max(dp1[i], fix2.first);
				if (fix3.second + (dpval[i - 1] + 0) == dpval[i] + 0) dp0[i] = max(dp0[i], fix3.first);
				if (fix3.second + (dpval[i - 1] + 0) == dpval[i] + 1) dp1[i] = max(dp1[i], fix3.first);
				if (fix4.second + (dpval[i - 1] + 1) == dpval[i] + 0) dp0[i] = max(dp0[i], fix4.first);
				if (fix4.second + (dpval[i - 1] + 1) == dpval[i] + 1) dp1[i] = max(dp1[i], fix4.first);
			}
			Answer[t] = dpval[Important.size() - 1];
			if (Answer[t] > 2 * H) Answer[t] = -1;
		}
	}

	// Step 8. 答えを返す
	return Answer;
}

// ==================================================================================================================================================== 入出力
int main() {
	// 入力
	int H, W, Q;
	scanf("%d%d%d", &H, &W, &Q);
	vector<vector<char>> A(H, vector<char>(W - 1, 0));
	vector<vector<char>> B(H - 1, vector<char>(W, 0));
	vector<vector<pair<int, int>>> Query(Q, vector<pair<int, int>>(0, make_pair(0, 0)));
	vector<int> C(H, 0);
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W - 1; j++) cin >> A[i][j];
	}
	for (int i = 0; i < H - 1; i++) {
		for (int j = 0; j < W; j++) cin >> B[i][j];
	}
	for (int i = 0; i < H; i++) cin >> C[i];
	for (int i = 0; i < Q; i++) {
		int t, x, y; scanf("%d", &t);
		for (int j = 0; j < t; j++) {
			scanf("%d%d", &x, &y); x--; y--;
			Query[i].push_back(make_pair(x, y));
		}
	}

	// 出力
	vector<int> Answer = solve_subtask8(H, W, Q, A, B, C, Query);
	for (int i = 0; i < Q; i++) printf("%d\n", Answer[i]);
	return 0;
}

Compilation message

Main.cpp:6: warning: ignoring '#pragma warning ' [-Wunknown-pragmas]
    6 | #pragma warning (disable: 4996)
      | 
Main.cpp: In function 'std::vector<std::pair<int, int> > OnlyMinimal(std::vector<std::pair<int, int> >)':
Main.cpp:57:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  for (int i = 0; i < Ranges.size(); i++) Ranges[i].first *= -1;
      |                  ~~^~~~~~~~~~~~~~~
Main.cpp:61:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for (int i = 0; i < Ranges.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
Main.cpp:67:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |  for (int i = 0; i < Return.size(); i++) Return[i].first *= -1;
      |                  ~~^~~~~~~~~~~~~~~
Main.cpp: In function 'std::vector<int> solve_subtask8(int, int, int, std::vector<std::vector<char> >, std::vector<std::vector<char> >, std::vector<int>, std::vector<std::vector<std::pair<int, int> > >)':
Main.cpp:217:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  217 |    for (int i = 1; i < Important.size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:254:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  254 |  scanf("%d%d%d", &H, &W, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:267:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  267 |   int t, x, y; scanf("%d", &t);
      |                ~~~~~^~~~~~~~~~
Main.cpp:269:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  269 |    scanf("%d%d", &x, &y); x--; y--;
      |    ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 354 ms 281432 KB Output is correct
3 Correct 86 ms 15044 KB Output is correct
4 Correct 73 ms 8592 KB Output is correct
5 Correct 100 ms 12428 KB Output is correct
6 Correct 104 ms 15508 KB Output is correct
7 Correct 359 ms 286292 KB Output is correct
8 Correct 381 ms 282196 KB Output is correct
9 Correct 363 ms 285536 KB Output is correct
10 Correct 83 ms 15088 KB Output is correct
11 Correct 254 ms 188804 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 354 ms 281432 KB Output is correct
3 Correct 86 ms 15044 KB Output is correct
4 Correct 73 ms 8592 KB Output is correct
5 Correct 100 ms 12428 KB Output is correct
6 Correct 104 ms 15508 KB Output is correct
7 Correct 359 ms 286292 KB Output is correct
8 Correct 381 ms 282196 KB Output is correct
9 Correct 363 ms 285536 KB Output is correct
10 Correct 83 ms 15088 KB Output is correct
11 Correct 254 ms 188804 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 360 ms 280916 KB Output is correct
14 Correct 164 ms 84048 KB Output is correct
15 Correct 96 ms 11604 KB Output is correct
16 Correct 99 ms 14932 KB Output is correct
17 Correct 77 ms 8528 KB Output is correct
18 Correct 346 ms 281948 KB Output is correct
19 Correct 345 ms 285008 KB Output is correct
20 Correct 85 ms 14260 KB Output is correct
21 Correct 266 ms 188544 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 354 ms 281432 KB Output is correct
3 Correct 86 ms 15044 KB Output is correct
4 Correct 73 ms 8592 KB Output is correct
5 Correct 100 ms 12428 KB Output is correct
6 Correct 104 ms 15508 KB Output is correct
7 Correct 359 ms 286292 KB Output is correct
8 Correct 381 ms 282196 KB Output is correct
9 Correct 363 ms 285536 KB Output is correct
10 Correct 83 ms 15088 KB Output is correct
11 Correct 254 ms 188804 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 360 ms 280916 KB Output is correct
14 Correct 164 ms 84048 KB Output is correct
15 Correct 96 ms 11604 KB Output is correct
16 Correct 99 ms 14932 KB Output is correct
17 Correct 77 ms 8528 KB Output is correct
18 Correct 346 ms 281948 KB Output is correct
19 Correct 345 ms 285008 KB Output is correct
20 Correct 85 ms 14260 KB Output is correct
21 Correct 266 ms 188544 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 361 ms 280792 KB Output is correct
24 Correct 431 ms 195424 KB Output is correct
25 Correct 152 ms 18464 KB Output is correct
26 Correct 119 ms 17664 KB Output is correct
27 Correct 137 ms 15852 KB Output is correct
28 Correct 428 ms 284708 KB Output is correct
29 Correct 401 ms 287612 KB Output is correct
30 Correct 376 ms 287536 KB Output is correct
31 Correct 377 ms 281944 KB Output is correct
32 Correct 413 ms 293664 KB Output is correct
33 Correct 134 ms 19184 KB Output is correct
34 Correct 299 ms 188496 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 354 ms 281432 KB Output is correct
3 Correct 86 ms 15044 KB Output is correct
4 Correct 73 ms 8592 KB Output is correct
5 Correct 100 ms 12428 KB Output is correct
6 Correct 104 ms 15508 KB Output is correct
7 Correct 359 ms 286292 KB Output is correct
8 Correct 381 ms 282196 KB Output is correct
9 Correct 363 ms 285536 KB Output is correct
10 Correct 83 ms 15088 KB Output is correct
11 Correct 254 ms 188804 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 360 ms 280916 KB Output is correct
14 Correct 164 ms 84048 KB Output is correct
15 Correct 96 ms 11604 KB Output is correct
16 Correct 99 ms 14932 KB Output is correct
17 Correct 77 ms 8528 KB Output is correct
18 Correct 346 ms 281948 KB Output is correct
19 Correct 345 ms 285008 KB Output is correct
20 Correct 85 ms 14260 KB Output is correct
21 Correct 266 ms 188544 KB Output is correct
22 Correct 757 ms 291792 KB Output is correct
23 Correct 540 ms 293388 KB Output is correct
24 Correct 342 ms 88680 KB Output is correct
25 Correct 244 ms 26004 KB Output is correct
26 Correct 248 ms 23208 KB Output is correct
27 Correct 313 ms 26192 KB Output is correct
28 Correct 121 ms 20052 KB Output is correct
29 Correct 643 ms 297296 KB Output is correct
30 Correct 576 ms 296788 KB Output is correct
31 Correct 624 ms 292944 KB Output is correct
32 Correct 623 ms 296088 KB Output is correct
33 Correct 219 ms 25332 KB Output is correct
34 Correct 510 ms 199584 KB Output is correct
35 Correct 505 ms 154104 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 354 ms 281432 KB Output is correct
3 Correct 86 ms 15044 KB Output is correct
4 Correct 73 ms 8592 KB Output is correct
5 Correct 100 ms 12428 KB Output is correct
6 Correct 104 ms 15508 KB Output is correct
7 Correct 359 ms 286292 KB Output is correct
8 Correct 381 ms 282196 KB Output is correct
9 Correct 363 ms 285536 KB Output is correct
10 Correct 83 ms 15088 KB Output is correct
11 Correct 254 ms 188804 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 360 ms 280916 KB Output is correct
14 Correct 164 ms 84048 KB Output is correct
15 Correct 96 ms 11604 KB Output is correct
16 Correct 99 ms 14932 KB Output is correct
17 Correct 77 ms 8528 KB Output is correct
18 Correct 346 ms 281948 KB Output is correct
19 Correct 345 ms 285008 KB Output is correct
20 Correct 85 ms 14260 KB Output is correct
21 Correct 266 ms 188544 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 361 ms 280792 KB Output is correct
24 Correct 431 ms 195424 KB Output is correct
25 Correct 152 ms 18464 KB Output is correct
26 Correct 119 ms 17664 KB Output is correct
27 Correct 137 ms 15852 KB Output is correct
28 Correct 428 ms 284708 KB Output is correct
29 Correct 401 ms 287612 KB Output is correct
30 Correct 376 ms 287536 KB Output is correct
31 Correct 377 ms 281944 KB Output is correct
32 Correct 413 ms 293664 KB Output is correct
33 Correct 134 ms 19184 KB Output is correct
34 Correct 299 ms 188496 KB Output is correct
35 Correct 757 ms 291792 KB Output is correct
36 Correct 540 ms 293388 KB Output is correct
37 Correct 342 ms 88680 KB Output is correct
38 Correct 244 ms 26004 KB Output is correct
39 Correct 248 ms 23208 KB Output is correct
40 Correct 313 ms 26192 KB Output is correct
41 Correct 121 ms 20052 KB Output is correct
42 Correct 643 ms 297296 KB Output is correct
43 Correct 576 ms 296788 KB Output is correct
44 Correct 624 ms 292944 KB Output is correct
45 Correct 623 ms 296088 KB Output is correct
46 Correct 219 ms 25332 KB Output is correct
47 Correct 510 ms 199584 KB Output is correct
48 Correct 505 ms 154104 KB Output is correct
49 Correct 903 ms 288592 KB Output is correct
50 Correct 767 ms 290128 KB Output is correct
51 Correct 309 ms 82256 KB Output is correct
52 Correct 142 ms 23856 KB Output is correct
53 Correct 143 ms 21448 KB Output is correct
54 Correct 185 ms 16404 KB Output is correct
55 Correct 421 ms 288032 KB Output is correct
56 Correct 462 ms 288548 KB Output is correct
57 Correct 375 ms 290756 KB Output is correct
58 Correct 516 ms 289284 KB Output is correct
59 Correct 121 ms 18928 KB Output is correct
60 Correct 676 ms 196276 KB Output is correct
61 Correct 652 ms 150976 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 354 ms 281432 KB Output is correct
3 Correct 86 ms 15044 KB Output is correct
4 Correct 73 ms 8592 KB Output is correct
5 Correct 100 ms 12428 KB Output is correct
6 Correct 104 ms 15508 KB Output is correct
7 Correct 359 ms 286292 KB Output is correct
8 Correct 381 ms 282196 KB Output is correct
9 Correct 363 ms 285536 KB Output is correct
10 Correct 83 ms 15088 KB Output is correct
11 Correct 254 ms 188804 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 360 ms 280916 KB Output is correct
14 Correct 164 ms 84048 KB Output is correct
15 Correct 96 ms 11604 KB Output is correct
16 Correct 99 ms 14932 KB Output is correct
17 Correct 77 ms 8528 KB Output is correct
18 Correct 346 ms 281948 KB Output is correct
19 Correct 345 ms 285008 KB Output is correct
20 Correct 85 ms 14260 KB Output is correct
21 Correct 266 ms 188544 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 361 ms 280792 KB Output is correct
24 Correct 431 ms 195424 KB Output is correct
25 Correct 152 ms 18464 KB Output is correct
26 Correct 119 ms 17664 KB Output is correct
27 Correct 137 ms 15852 KB Output is correct
28 Correct 428 ms 284708 KB Output is correct
29 Correct 401 ms 287612 KB Output is correct
30 Correct 376 ms 287536 KB Output is correct
31 Correct 377 ms 281944 KB Output is correct
32 Correct 413 ms 293664 KB Output is correct
33 Correct 134 ms 19184 KB Output is correct
34 Correct 299 ms 188496 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 349 ms 280928 KB Output is correct
38 Correct 374 ms 280920 KB Output is correct
39 Correct 346 ms 282204 KB Output is correct
40 Correct 285 ms 131064 KB Output is correct
41 Correct 129 ms 20276 KB Output is correct
42 Correct 135 ms 16496 KB Output is correct
43 Correct 375 ms 283848 KB Output is correct
44 Correct 377 ms 289640 KB Output is correct
45 Correct 403 ms 290968 KB Output is correct
46 Correct 366 ms 281940 KB Output is correct
47 Correct 409 ms 293456 KB Output is correct
48 Correct 363 ms 283184 KB Output is correct
49 Correct 112 ms 18476 KB Output is correct
50 Correct 261 ms 188552 KB Output is correct
51 Correct 278 ms 188532 KB Output is correct
52 Correct 212 ms 143184 KB Output is correct
53 Correct 243 ms 143248 KB Output is correct

Subtask #7
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 354 ms 281432 KB Output is correct
3 Correct 86 ms 15044 KB Output is correct
4 Correct 73 ms 8592 KB Output is correct
5 Correct 100 ms 12428 KB Output is correct
6 Correct 104 ms 15508 KB Output is correct
7 Correct 359 ms 286292 KB Output is correct
8 Correct 381 ms 282196 KB Output is correct
9 Correct 363 ms 285536 KB Output is correct
10 Correct 83 ms 15088 KB Output is correct
11 Correct 254 ms 188804 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 360 ms 280916 KB Output is correct
14 Correct 164 ms 84048 KB Output is correct
15 Correct 96 ms 11604 KB Output is correct
16 Correct 99 ms 14932 KB Output is correct
17 Correct 77 ms 8528 KB Output is correct
18 Correct 346 ms 281948 KB Output is correct
19 Correct 345 ms 285008 KB Output is correct
20 Correct 85 ms 14260 KB Output is correct
21 Correct 266 ms 188544 KB Output is correct
22 Correct 757 ms 291792 KB Output is correct
23 Correct 540 ms 293388 KB Output is correct
24 Correct 342 ms 88680 KB Output is correct
25 Correct 244 ms 26004 KB Output is correct
26 Correct 248 ms 23208 KB Output is correct
27 Correct 313 ms 26192 KB Output is correct
28 Correct 121 ms 20052 KB Output is correct
29 Correct 643 ms 297296 KB Output is correct
30 Correct 576 ms 296788 KB Output is correct
31 Correct 624 ms 292944 KB Output is correct
32 Correct 623 ms 296088 KB Output is correct
33 Correct 219 ms 25332 KB Output is correct
34 Correct 510 ms 199584 KB Output is correct
35 Correct 505 ms 154104 KB Output is correct
36 Correct 0 ms 344 KB Output is correct
37 Correct 246 ms 188528 KB Output is correct
38 Correct 205 ms 143232 KB Output is correct
39 Correct 742 ms 291712 KB Output is correct
40 Correct 486 ms 293252 KB Output is correct
41 Correct 478 ms 293200 KB Output is correct
42 Correct 318 ms 86868 KB Output is correct
43 Correct 226 ms 25728 KB Output is correct
44 Correct 254 ms 22980 KB Output is correct
45 Correct 222 ms 26316 KB Output is correct
46 Correct 118 ms 19912 KB Output is correct
47 Correct 607 ms 297300 KB Output is correct
48 Correct 591 ms 296840 KB Output is correct
49 Correct 632 ms 292952 KB Output is correct
50 Correct 652 ms 295972 KB Output is correct
51 Correct 158 ms 25328 KB Output is correct
52 Correct 590 ms 292948 KB Output is correct
53 Correct 502 ms 199504 KB Output is correct
54 Correct 443 ms 154288 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 354 ms 281432 KB Output is correct
3 Correct 86 ms 15044 KB Output is correct
4 Correct 73 ms 8592 KB Output is correct
5 Correct 100 ms 12428 KB Output is correct
6 Correct 104 ms 15508 KB Output is correct
7 Correct 359 ms 286292 KB Output is correct
8 Correct 381 ms 282196 KB Output is correct
9 Correct 363 ms 285536 KB Output is correct
10 Correct 83 ms 15088 KB Output is correct
11 Correct 254 ms 188804 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 360 ms 280916 KB Output is correct
14 Correct 164 ms 84048 KB Output is correct
15 Correct 96 ms 11604 KB Output is correct
16 Correct 99 ms 14932 KB Output is correct
17 Correct 77 ms 8528 KB Output is correct
18 Correct 346 ms 281948 KB Output is correct
19 Correct 345 ms 285008 KB Output is correct
20 Correct 85 ms 14260 KB Output is correct
21 Correct 266 ms 188544 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 361 ms 280792 KB Output is correct
24 Correct 431 ms 195424 KB Output is correct
25 Correct 152 ms 18464 KB Output is correct
26 Correct 119 ms 17664 KB Output is correct
27 Correct 137 ms 15852 KB Output is correct
28 Correct 428 ms 284708 KB Output is correct
29 Correct 401 ms 287612 KB Output is correct
30 Correct 376 ms 287536 KB Output is correct
31 Correct 377 ms 281944 KB Output is correct
32 Correct 413 ms 293664 KB Output is correct
33 Correct 134 ms 19184 KB Output is correct
34 Correct 299 ms 188496 KB Output is correct
35 Correct 757 ms 291792 KB Output is correct
36 Correct 540 ms 293388 KB Output is correct
37 Correct 342 ms 88680 KB Output is correct
38 Correct 244 ms 26004 KB Output is correct
39 Correct 248 ms 23208 KB Output is correct
40 Correct 313 ms 26192 KB Output is correct
41 Correct 121 ms 20052 KB Output is correct
42 Correct 643 ms 297296 KB Output is correct
43 Correct 576 ms 296788 KB Output is correct
44 Correct 624 ms 292944 KB Output is correct
45 Correct 623 ms 296088 KB Output is correct
46 Correct 219 ms 25332 KB Output is correct
47 Correct 510 ms 199584 KB Output is correct
48 Correct 505 ms 154104 KB Output is correct
49 Correct 903 ms 288592 KB Output is correct
50 Correct 767 ms 290128 KB Output is correct
51 Correct 309 ms 82256 KB Output is correct
52 Correct 142 ms 23856 KB Output is correct
53 Correct 143 ms 21448 KB Output is correct
54 Correct 185 ms 16404 KB Output is correct
55 Correct 421 ms 288032 KB Output is correct
56 Correct 462 ms 288548 KB Output is correct
57 Correct 375 ms 290756 KB Output is correct
58 Correct 516 ms 289284 KB Output is correct
59 Correct 121 ms 18928 KB Output is correct
60 Correct 676 ms 196276 KB Output is correct
61 Correct 652 ms 150976 KB Output is correct
62 Correct 0 ms 348 KB Output is correct
63 Correct 0 ms 348 KB Output is correct
64 Correct 349 ms 280928 KB Output is correct
65 Correct 374 ms 280920 KB Output is correct
66 Correct 346 ms 282204 KB Output is correct
67 Correct 285 ms 131064 KB Output is correct
68 Correct 129 ms 20276 KB Output is correct
69 Correct 135 ms 16496 KB Output is correct
70 Correct 375 ms 283848 KB Output is correct
71 Correct 377 ms 289640 KB Output is correct
72 Correct 403 ms 290968 KB Output is correct
73 Correct 366 ms 281940 KB Output is correct
74 Correct 409 ms 293456 KB Output is correct
75 Correct 363 ms 283184 KB Output is correct
76 Correct 112 ms 18476 KB Output is correct
77 Correct 261 ms 188552 KB Output is correct
78 Correct 278 ms 188532 KB Output is correct
79 Correct 212 ms 143184 KB Output is correct
80 Correct 243 ms 143248 KB Output is correct
81 Correct 0 ms 344 KB Output is correct
82 Correct 246 ms 188528 KB Output is correct
83 Correct 205 ms 143232 KB Output is correct
84 Correct 742 ms 291712 KB Output is correct
85 Correct 486 ms 293252 KB Output is correct
86 Correct 478 ms 293200 KB Output is correct
87 Correct 318 ms 86868 KB Output is correct
88 Correct 226 ms 25728 KB Output is correct
89 Correct 254 ms 22980 KB Output is correct
90 Correct 222 ms 26316 KB Output is correct
91 Correct 118 ms 19912 KB Output is correct
92 Correct 607 ms 297300 KB Output is correct
93 Correct 591 ms 296840 KB Output is correct
94 Correct 632 ms 292952 KB Output is correct
95 Correct 652 ms 295972 KB Output is correct
96 Correct 158 ms 25328 KB Output is correct
97 Correct 590 ms 292948 KB Output is correct
98 Correct 502 ms 199504 KB Output is correct
99 Correct 443 ms 154288 KB Output is correct
100 Correct 933 ms 288756 KB Output is correct
101 Correct 772 ms 290136 KB Output is correct
102 Correct 806 ms 290280 KB Output is correct
103 Correct 372 ms 83280 KB Output is correct
104 Correct 163 ms 53616 KB Output is correct
105 Correct 139 ms 21380 KB Output is correct
106 Correct 139 ms 16996 KB Output is correct
107 Correct 404 ms 285320 KB Output is correct
108 Correct 394 ms 292668 KB Output is correct
109 Correct 368 ms 290936 KB Output is correct
110 Correct 473 ms 289268 KB Output is correct
111 Correct 359 ms 286496 KB Output is correct
112 Correct 118 ms 19016 KB Output is correct
113 Correct 688 ms 196432 KB Output is correct
114 Correct 572 ms 151120 KB Output is correct