Submission #138432

#	Time	Username	Problem	Language	Result	Execution time	Memory
138432		arthurconmy	Roller Coaster Railroad (IOI16_railroad)	C++14	0 / 100	675 ms	273396 KiB

railroad

#include <bits/stdc++.h>
#ifndef ARTHUR_LOCAL
	#include "railroad.h"
#endif
using namespace std;
using ll=long long;

ll dp[65536][16][16];
vector<int> masks[17];

ll plan_roller_coaster(vector<int> S, vector<int> T) 
{
	int n = S.size();

	for(int i=0; i<65536; i++)
	{
		for(int j=0; j<16; j++)
		{
			for(int k=0; k<16; k++)
			{
				dp[i][j][k]=1e18;
			}
		}
	}

	for(int i=0; i<16; i++)
	{
		dp[1<<i][i][i] = 0;
	}

	for(int i=0; i<65536; i++)
	{
		int cnt=0;

		for(int j=0; j<16; j++)
		{
			if(i & (1<<j)) cnt++;
		}

		masks[cnt].push_back(i);

		// if(i<100) cout << i << " " << cnt << endl;
	}

	ll ans=1e18;

	for(int len=2; len<=n; len++)
	{
		for(int i=0; i<masks[len].size(); i++)
		{
			vector<int> curs;

			for(int j=0; j<16; j++)
			{
				if(masks[len][i] & (1<<j)) curs.push_back(j);
			}

			for(int j=0; j<curs.size(); j++)
			{
				for(int k=0; k<curs.size(); k++)
				{
					if(j==k) continue;
				
					int l=curs[j];
					int r=curs[k];

					for(int m=0; m<16; m++)
					{
						if((masks[len][i] & m) == 0) continue;
						if(m==r) continue;
						if(m==l && len!=2) continue;

						dp[masks[len][i]][l][r] = min(dp[masks[len][i]][l][r], dp[masks[len][i] - (1<<r)][l][m] + max(0,T[r]-S[m]));
					}

					if(len==n) ans=min(ans,dp[masks[len][i]][l][r]);
				}
			}
		}
	}

	return ans;
}

#ifdef ARTHUR_LOCAL
	int main()
	{
		cout << plan_roller_coaster({1, 4, 5, 6}, {7, 3, 8, 6}) << endl;
	}
#endif

Compilation message (stderr)

railroad.cpp: In function 'll plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:49:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<masks[len].size(); i++)
                ~^~~~~~~~~~~~~~~~~~
railroad.cpp:58:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0; j<curs.size(); j++)
                 ~^~~~~~~~~~~~
railroad.cpp:60:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int k=0; k<curs.size(); k++)
                  ~^~~~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 23
• Subtask 3: 0 / 30
• Subtask 4: 0 / 36