Submission #72607

#	Time	Username	Problem	Language	Result	Execution time	Memory
72607		aleksam	Roller Coaster Railroad (IOI16_railroad)	C++14	34 / 100	117 ms	17924 KiB

railroad

#pragma once

#include <bits/stdc++.h>
#define MAX_N 16
#define INF 987654321987654321

using namespace std;

int N;
long long D[1<<MAX_N][MAX_N];
vector<long long> s, t;
void init(){
	for(int i=0; i<N; ++i){
		for(int j=0; j<(1<<N); ++j){
			D[j][i]=-1;
		}
	}
	for(int i=0; i<N; ++i){
		D[1<<i][i]=0;
	}
}

long long relu(long long v){
	return v>0?v:0;
}

long long dp(int mask, int v){
	//printf("mask=%d v=%d\n", mask, v);
	if(D[mask][v]!=-1LL)return D[mask][v];
	assert(mask&& (1<<v));
	long long mini=INF;
	for(int i=0; i<N; ++i){
		
		if(((mask&(1<<i))!=0) && (i!=v)){
			if(dp(mask^(1<<v), i)+relu(t[v]-s[i])<mini){
				
				mini=dp(mask^(1<<v), i)+relu(t[v]-s[i]);
				//printf("Pri (%d), mini=%lld\n", i, mini); 
			}
		}
	}
	//printf("RET\n");
	D[mask][v]=mini;
	//printf("D[%d][%d]=%lld\n", mask, v, D[mask][v]);
	return D[mask][v];
}

long long plan_roller_coaster(vector<int> S, vector<int> T) {
	N=S.size();
	for(int i=0; i<N; ++i){
		s.push_back((long long)S[i]);
		t.push_back((long long)T[i]);
	}
	init();
	long long mini=INF;
	for(int i=0; i<N; ++i){
		
		if(dp((1<<N)-1, i)<mini){
			mini=dp((1<<N)-1, i);
		}
	}
    return mini;
}

Compilation message (stderr)

railroad.cpp:1:9: warning: #pragma once in main file
 #pragma once
         ^~~~
In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from railroad.cpp:3:
railroad.cpp: In function 'long long int dp(int, int)':
railroad.cpp:30:18: warning: '<<' in boolean context, did you mean '<' ? [-Wint-in-bool-context]
  assert(mask&& (1<<v));
                ~~^~~~

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