Submission #52770

# Submission time Handle Problem Language Result Execution time Memory
52770 2018-06-26T17:40:00 Z KieranHorgan Wiring (IOI17_wiring) C++17
0 / 100
1000 ms 57964 KB
#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long

int n, m, ans;
vector<int> fullList;
unordered_map<int, bool> isRed, isBlue;
vector<vector<int>> segments;
vector<vector<int>> prefixR;
vector<vector<int>> prefixL;

int calcWire(int s, int l, int r) {
	int res = 0;
	res += prefixL[s][l];
	res += (segments[s].size()-l) * (segments[s+1][0]-segments[s].back());
	res += prefixR[s+1][r];
	res += (r+1) * (segments[s+1][0]-segments[s].back());
	res -= min((int)segments[s].size()-l, r+1)*(segments[s+1][0]-segments[s].back());
	return res;
}

int dp[205][205];

long long min_total_length(vector<signed> r, vector<signed> b) {
	n = r.size();
	m = b.size();
	fullList.resize(n+m);
	merge(r.begin(), r.end(), b.begin(), b.end(), fullList.begin());
	for(auto x: r)
		isRed[x]=1;
	for(auto x: b)
		isBlue[x]=1;

	for(int i = 0; i < m+n; i++) {
		if(i==0 || isRed[fullList[i]] != isRed[fullList[i-1]]) {
			segments.push_back(vector<int>(0));
			prefixL.push_back(vector<int>(0));
			prefixR.push_back(vector<int>(0));
			segments.back().push_back(fullList[i]);
		} else {
			segments.back().push_back(fullList[i]);
		}
	}

	for(int s = 0; s < segments.size(); s++) {
		prefixR[s].push_back(0);
		for(int i = 1; i < segments[s].size(); i++)
			prefixR[s].push_back(prefixR[s][i-1]+segments[s][i]-segments[s][0]);
		reverse(segments[s].begin(), segments[s].end());
		prefixL[s].push_back(0);
		for(int i = 1; i < segments[s].size(); i++)
			prefixL[s].push_back(prefixL[s][i-1]+segments[s][0]-segments[s][i]);
		reverse(prefixL[s].begin(), prefixL[s].end());
		reverse(segments[s].begin(), segments[s].end());
	}

	memset(dp, 63, sizeof(dp));
	for(int j = 0; j < segments[1].size(); j++)
		dp[1][j] = calcWire(0, 0, j);

	for(int s = 2; s < segments.size(); s++) {
		for(int i = 0; i < segments[s].size(); i++) {
			dp[s][i] = min(dp[s][i], dp[s-2][segments[s-2].size()-1] + calcWire(s-1, 0, i));
			for(int j = 1; j < segments[s-1].size(); j++)
				dp[s][i] = min(dp[s][i], dp[s-1][j-1] + calcWire(s-1, j, i));
		}
	}

	return dp[segments.size()-1][segments.back().size()-1];
	if(segments.size() == 2)
		return calcWire(0, 0, m-1);
	return -1;
}

Compilation message

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:46:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int s = 0; s < segments.size(); s++) {
                 ~~^~~~~~~~~~~~~~~~~
wiring.cpp:48:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 1; i < segments[s].size(); i++)
                  ~~^~~~~~~~~~~~~~~~~~~~
wiring.cpp:52:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 1; i < segments[s].size(); i++)
                  ~~^~~~~~~~~~~~~~~~~~~~
wiring.cpp:59:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j = 0; j < segments[1].size(); j++)
                 ~~^~~~~~~~~~~~~~~~~~~~
wiring.cpp:62:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int s = 2; s < segments.size(); s++) {
                 ~~^~~~~~~~~~~~~~~~~
wiring.cpp:63:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < segments[s].size(); i++) {
                  ~~^~~~~~~~~~~~~~~~~~~~
wiring.cpp:65:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 1; j < segments[s-1].size(); j++)
                   ~~^~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Incorrect 3 ms 780 KB 3rd lines differ - on the 1st token, expected: '14340', found: '14694'
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 3 ms 780 KB Output is correct
2 Correct 3 ms 780 KB Output is correct
3 Runtime error 117 ms 31072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 3 ms 31072 KB Output is correct
2 Correct 2 ms 31072 KB Output is correct
3 Runtime error 237 ms 57964 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 3 ms 57964 KB Output is correct
2 Execution timed out 1068 ms 57964 KB Time limit exceeded
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Incorrect 3 ms 780 KB 3rd lines differ - on the 1st token, expected: '14340', found: '14694'
3 Halted 0 ms 0 KB -