Submission #284354

#	Time	Username	Problem	Language	Result	Execution time	Memory
284354		Berted	Wiring (IOI17_wiring)	C++14	7 / 100	41 ms	5624 KiB

wiring

#include "wiring.h"
#include <vector>
#include <stack>
#include <algorithm>
#include <assert.h>
#define ll long long
#define pii pair<int, int>
#define fst first
#define snd second

using namespace std;

const ll INF = 1e9 + 7, INF2 = 1e18 + 7;

vector<pii> A;
int C[401];
ll ret = 0;
ll dp[401][401][2];


ll min_total_length(vector<int> r, vector<int> b) 
{
	int i = 0, j = 0;
	while (i < r.size() || j < b.size())
	{
		int valL = (i < r.size()) ? r[i] : INF;
		int valR = (j < b.size()) ? b[j] : INF;
		if (valL < valR) 
		{
			A.push_back({valL, 0}); 
			C[A.size() - 1] = INF;
			if (j < b.size()) {C[A.size() - 1] = min(C[A.size() - 1], b[j] - valL);}
			if (j) {C[A.size() - 1] = min(C[A.size() - 1], valL - b[j - 1]);}
			i++;
		} 
		else 
		{
			A.push_back({valR, 1}); 
			C[A.size() - 1] = INF;
			if (i < r.size()) {C[A.size() - 1] = min(C[A.size() - 1], r[i] - valR);}
			if (i) {C[A.size() - 1] = min(C[A.size() - 1], valR - r[i - 1]);}
			j++;
		}
	} 
	for (int i = 0; i <= A.size(); i++)
	{
		for (int j = 0; j <= A.size(); j++) {dp[i][j][0] = dp[i][j][1] = INF2;}
	}
	dp[0][0][0] = 0;
	for (int i = 0; i < A.size(); i++)
	{
		for (int j = 0; j <= A.size(); j++)
		{
			for (int k = 0; k < 2; k++)
			{
				if (j == 0 && k) continue;
				dp[i + 1][j][k] = min(dp[i + 1][j][k], dp[i][j][k] + C[i]);
				if (j)
				{
					if (A[i].snd == k) {dp[i + 1][j + 1][k] = min(dp[i + 1][j + 1][k], dp[i][j][k] - A[i].fst);}
					else {dp[i + 1][j - 1][(j > 1) ? k : 0] = min(dp[i + 1][j - 1][(j > 1) ? k : 0], dp[i][j][k] + A[i].fst);}
				}
				else
				{
					dp[i + 1][j + 1][A[i].snd] = min(dp[i + 1][j + 1][A[i].snd], dp[i][j][k] - A[i].fst);
				}
			}
		}
	}
	return dp[A.size()][0][0];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:24:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  while (i < r.size() || j < b.size())
      |         ~~^~~~~~~~~~
wiring.cpp:24:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  while (i < r.size() || j < b.size())
      |                         ~~^~~~~~~~~~
wiring.cpp:26:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |   int valL = (i < r.size()) ? r[i] : INF;
      |               ~~^~~~~~~~~~
wiring.cpp:27:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |   int valR = (j < b.size()) ? b[j] : INF;
      |               ~~^~~~~~~~~~
wiring.cpp:32:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |    if (j < b.size()) {C[A.size() - 1] = min(C[A.size() - 1], b[j] - valL);}
      |        ~~^~~~~~~~~~
wiring.cpp:40:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |    if (i < r.size()) {C[A.size() - 1] = min(C[A.size() - 1], r[i] - valR);}
      |        ~~^~~~~~~~~~
wiring.cpp:45: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]
   45 |  for (int i = 0; i <= A.size(); i++)
      |                  ~~^~~~~~~~~~~
wiring.cpp:47:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for (int j = 0; j <= A.size(); j++) {dp[i][j][0] = dp[i][j][1] = INF2;}
      |                   ~~^~~~~~~~~~~
wiring.cpp:50: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]
   50 |  for (int i = 0; i < A.size(); i++)
      |                  ~~^~~~~~~~~~
wiring.cpp:52:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   for (int j = 0; j <= A.size(); j++)
      |                   ~~^~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 0 / 13
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45