Submission #132812

#	Time	Username	Problem	Language	Result	Execution time	Memory
132812		DanerZein	Roller Coaster Railroad (IOI16_railroad)	C++14	0 / 100	120 ms	42292 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
#define MAX 1000000002
using namespace std;
long long dp[20][100000];
long long dist[20][20];
long long l,tam;
long long tsp(int id,long long mask){
  // cout<<id<<" "<<mask<<" "<<endl;
  if(mask==l)return 0;
  if(dp[id][mask]!=-1){
    return dp[id][mask];
  }
  long long r=MAX;
  for(int i=0;i<tam;i++){
    if((mask & (1<<i))==0){
      long long newmask=mask|(1<<i);
      r=min(r,tsp(i,newmask)+dist[id][i]);
    }
  }
  return dp[id][mask]=r;
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
  tam=t.size();
  memset(dp,-1,sizeof dp);
  for(long long i=0;i<s.size();i++){
    for(long long j=i+1;j<s.size();j++){
      long long d=t[i]-s[j];
      if(d>=0){
	dist[i][j]=d;
      }
      else{
	dist[i][j]=0;
      }
      d=t[j]-s[i];
      if(d>=0){
	dist[j][i]=d;
      }
      else{
	dist[j][i]=0;
      }
    }
  }
  /*for(int i=0;i<t.size();i++){
    for(int j=0;j<t.size();j++){
      cout<<dist[i][j]<<" ";
    }
    cout<<endl;
    }*/
  l=(1<<s.size())-1;
  long long r=tsp(0,1);
  return r;
}

Compilation message (stderr)

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:26:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(long long i=0;i<s.size();i++){
                     ~^~~~~~~~~
railroad.cpp:27:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(long long j=i+1;j<s.size();j++){
                         ~^~~~~~~~~

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