Submission #425268

#	Time	Username	Problem	Language	Result	Execution time	Memory
425268		Ahmadsm2005	Roller Coaster Railroad (IOI16_railroad)	C++14	34 / 100	96 ms	34860 KiB

railroad

#include "railroad.h"
//#include "grader.cpp"
#include<bits/stdc++.h>
using namespace std;
long long DP[65536][17];
vector<pair<long long,long long>>lolz;
long long REC(int MASK,int LAST){
if(DP[MASK][LAST]+1)
return DP[MASK][LAST];
long long BEST=(long long)4e18;
for(int i=0;i<lolz.size();i++){
if(!(MASK&(1<<i))){
BEST=min(BEST,REC(MASK|(1<<i),i)+max((long long)0,lolz[LAST].second-lolz[i].first));
}
}
if(BEST==4e18)
BEST=0;
return DP[MASK][LAST]=BEST;
}
long long plan_roller_coaster(vector<int>s,vector<int>t){
for(int i=0;i<65536;i++)
for(int l=0;l<17;l++)
DP[i][l]=-1;
for(int i=0;i<s.size();i++)
lolz.push_back({s[i],t[i]});
sort(lolz.begin(),lolz.end());
long long M=(long long)4e18;
for(int i=0;i<s.size();i++){
M=min(M,REC((1<<i),i));
}
return M;
}

Compilation message (stderr)

railroad.cpp: In function 'long long int REC(int, int)':
railroad.cpp:11:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | for(int i=0;i<lolz.size();i++){
      |             ~^~~~~~~~~~~~
railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:24:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 | for(int i=0;i<s.size();i++)
      |             ~^~~~~~~~~
railroad.cpp:28:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 | for(int i=0;i<s.size();i++){
      |             ~^~~~~~~~~

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