oj.uz

Submission #113476

# Submission time Handle Problem Language Result Execution time Memory
113476 2019-05-25T21:36:06 Z E869120 Wiring (IOI17_wiring) C++14
20 / 100
 33 ms 5496 KB 
#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;

long long N, M, A[200009], B[200009], dp[2009][2009];

long long solve_subtask1() {
	for (int i = 0; i <= N; i++) {
		for (int j = 0; j <= M; j++) dp[i][j] = (1LL << 60);
	}
	dp[0][0] = 0;
	for (int i = 0; i <= N; i++) {
		for (int j = 0; j <= M; j++) {
			dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + abs(A[i] - B[j]));
			if (j >= 1) dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + abs(A[i] - B[j - 1]));
			if (i >= 1) dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + abs(A[i - 1] - B[j]));
		}
	}
	return dp[N][M];
}

long long solve_subtask2() {
	long long sum = 0;
	for (int i = 0; i < N - 1; i++) sum += 1LL * (i + 1LL) * (A[i + 1] - A[i]);
	for (int i = 0; i < M - 1; i++) sum += 1LL * (M - i - 1LL) * (B[i + 1] - B[i]);
	sum += 1LL * max(N, M) * (B[0] - A[N - 1]);
	return sum;
}

long long min_total_length(vector<int> r, vector<int> b) {
	N = r.size(); M = b.size();
	for (int i = 0; i < N; i++) A[i] = r[i];
	for (int i = 0; i < M; i++) B[i] = b[i];
	
	if (N <= 2000 && M <= 2000) return solve_subtask1();
	return solve_subtask2();
}

Subtask #1
7.0 / 7.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 1280 KB Output is correct
3 Correct 23 ms 2680 KB Output is correct
4 Correct 24 ms 4088 KB Output is correct
5 Correct 24 ms 4088 KB Output is correct
6 Correct 30 ms 5372 KB Output is correct
7 Correct 31 ms 5380 KB Output is correct
8 Correct 31 ms 5368 KB Output is correct
9 Correct 32 ms 5496 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Incorrect 30 ms 3448 KB 3rd lines differ - on the 1st token, expected: '1068938599', found: '-303948787415'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 33 ms 3468 KB 3rd lines differ - on the 1st token, expected: '373710605', found: '2074975518'
3 Halted 0 ms 0 KB -

Subtask #5
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 1536 KB Output is correct
8 Correct 2 ms 1408 KB Output is correct
9 Correct 3 ms 1408 KB Output is correct
10 Correct 2 ms 1408 KB Output is correct
11 Correct 3 ms 1536 KB Output is correct
12 Correct 3 ms 1536 KB Output is correct
13 Correct 3 ms 1536 KB Output is correct
14 Correct 3 ms 1536 KB Output is correct
15 Correct 3 ms 1408 KB Output is correct
16 Correct 3 ms 1536 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 3 ms 1280 KB Output is correct
19 Correct 23 ms 2680 KB Output is correct
20 Correct 24 ms 4088 KB Output is correct
21 Correct 24 ms 4088 KB Output is correct
22 Correct 30 ms 5372 KB Output is correct
23 Correct 31 ms 5380 KB Output is correct
24 Correct 31 ms 5368 KB Output is correct
25 Correct 32 ms 5496 KB Output is correct
26 Correct 2 ms 384 KB Output is correct
27 Correct 2 ms 384 KB Output is correct
28 Incorrect 30 ms 3448 KB 3rd lines differ - on the 1st token, expected: '1068938599', found: '-303948787415'
29 Halted 0 ms 0 KB -