oj.uz

Submission #33898

# Submission time Handle Problem Language Result Execution time Memory
33898 2017-11-04T16:22:50 Z mohammad_kilani Wiring (IOI17_wiring) C++14
20 / 100
 43 ms 6324 KB 
#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 500;
vector<int> r , b;
long long dp[N][N];
int n , m;
long long solve(int i,int j){
	if(i == n && j == m) return 0;
	if(j == m) return 1e18;
	if(dp[i][j] != -1) return dp[i][j];
	dp[i][j] = min(solve(i+1,j),min(solve(i,j+1),solve(i+1,j+1))) + abs(r[i] - b[j]);
	return dp[i][j];
}




long long min_total_length(std::vector<int> R, std::vector<int> B) {
	memset(dp,-1,sizeof(dp));
	r = R;
	b = B;
	n = r.size();
	m = b.size();
	if(n <= 500 && m <= 500) return solve(0,0);
	if(r.back() < b[0]){
		long long sum = 0 ;
		int idx = 0 ;
		int idx2 = 0;
		for(int i=0;i<min(n,m);i++) sum += abs(r[idx++] - b[idx2++]);
		for(int i=idx;i<r.size();i++) sum+= abs(r[i] - b[0]);
		for(int i=idx2;i<b.size();i++) sum+= abs(b[i] - r.back());
		return sum;
	}
	return rand();

}

Compilation message

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:31:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=idx;i<r.size();i++) sum+= abs(r[i] - b[0]);
                  ^
wiring.cpp:32:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=idx2;i<b.size();i++) sum+= abs(b[i] - r.back());
                   ^

Subtask #1
7.0 / 7.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3972 KB Output is correct
2 Correct 0 ms 3972 KB Output is correct
3 Correct 36 ms 5736 KB Output is correct
4 Correct 43 ms 5736 KB Output is correct
5 Correct 23 ms 5736 KB Output is correct
6 Correct 43 ms 6324 KB Output is correct
7 Correct 33 ms 6324 KB Output is correct
8 Correct 36 ms 6324 KB Output is correct
9 Correct 36 ms 6324 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 25.0

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

Subtask #5
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3972 KB Output is correct
2 Correct 0 ms 3972 KB Output is correct
3 Correct 0 ms 3972 KB Output is correct
4 Correct 0 ms 3972 KB Output is correct
5 Correct 0 ms 3972 KB Output is correct
6 Correct 0 ms 3972 KB Output is correct
7 Correct 3 ms 3972 KB Output is correct
8 Correct 3 ms 3972 KB Output is correct
9 Correct 3 ms 3972 KB Output is correct
10 Correct 0 ms 3972 KB Output is correct
11 Correct 0 ms 3972 KB Output is correct
12 Correct 3 ms 3972 KB Output is correct
13 Correct 3 ms 3972 KB Output is correct
14 Correct 0 ms 3972 KB Output is correct
15 Correct 3 ms 3972 KB Output is correct
16 Correct 0 ms 3972 KB Output is correct
17 Correct 0 ms 3972 KB Output is correct
18 Correct 0 ms 3972 KB Output is correct
19 Correct 36 ms 5736 KB Output is correct
20 Correct 43 ms 5736 KB Output is correct
21 Correct 23 ms 5736 KB Output is correct
22 Correct 43 ms 6324 KB Output is correct
23 Correct 33 ms 6324 KB Output is correct
24 Correct 36 ms 6324 KB Output is correct
25 Correct 36 ms 6324 KB Output is correct
26 Correct 0 ms 3972 KB Output is correct
27 Correct 0 ms 3972 KB Output is correct
28 Incorrect 33 ms 6324 KB 3rd lines differ - on the 1st token, expected: '1068938599', found: '1804289383'
29 Halted 0 ms 0 KB -