oj.uz

Submission #50265

# Submission time Handle Problem Language Result Execution time Memory
50265 2018-06-08T20:23:02 Z Bruteforceman Wiring (IOI17_wiring) C++11
0 / 100
 20 ms 19236 KB 
#include "bits/stdc++.h"
#include "wiring.h"
using namespace std;
const long long inf = 1e15;

vector <long long> dp[200010];
vector <int> group[200010];
vector <long long> first[200010], last[200010];
typedef pair <int, int> pii;

long long min_total_length(std::vector<int> r, std::vector<int> b) {
	int g = 0;
	int n = r.size();
	int m = b.size();
	vector <pii> v;
	for(int i = 0; i < n; i++) {
		v.emplace_back(r[i], 0);
	}
	for(int i = 0; i < m; i++) {
		v.emplace_back(b[i], 1);
	}
	sort(v.begin(), v.end());
	int prevc = -1;
	group[0].push_back(-1);
	for(int i = 0; i < n+m; i++) {
		if(prevc == v[i].second) {
			group[g].push_back(v[i].first);
		} else {
			++g;
			prevc = v[i].second;
			group[g].push_back(-1);
			group[g].push_back(v[i].first);
		}
	}
	for(int i = 0; i <= g; i++) {
		int sz = group[i].size() - 1;
		first[i].resize(sz + 1);
		last[i].resize(sz + 1);
		for(int j = 1; j <= sz; j++) {
			first[i][j] = first[i][j - 1] + group[i][j];
			last[i][j] = last[i][j - 1] + group[i][sz - j + 1];
		}
	}
	for(int i = 1; i <= g+1; i++) {
		int sz = group[i - 1].size() - 1;
		dp[i].resize(sz + 1);
		for(int j = 0; j <= sz; j++) {
			dp[i][j] = inf;
		}
	}
	
	for(int i = 0; i <= g; i++) {
		for(int j : group[i]) {
			cout << j << " ";
		}
		cout << endl;
	}
	dp[1][0] = 0;
	for(int i = 1; i <= g; i++) {
		int sz_prev = group[i - 1].size() - 1;
		int sz_cur = group[i].size() - 1;
		for(int j = sz_prev; j > 0; j--) {
			dp[i][j - 1] = min(dp[i][j - 1], dp[i][j] + abs(group[i - 1][sz_prev - j + 1] - group[i][1]));
		}
		for(int j = 0; j <= min(sz_cur, sz_prev); j++) {
			dp[i + 1][sz_cur - j] = min(dp[i + 1][sz_cur - j], dp[i][j] + abs(last[i - 1][j] - first[i][j]));
		}
		for(int j = sz_cur; j > 0; j--) {
			if(i == 1) break;
			dp[i + 1][j - 1] = min(dp[i + 1][j - 1], dp[i + 1][j] + abs(group[i][sz_cur - j + 1] - group[i - 1].back()));
		}
	}
	return dp[g + 1][0];
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 19064 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 19184 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 19236 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 19236 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #5
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 19064 KB secret mismatch
2 Halted 0 ms 0 KB -