Submission #545684

#	Time	Username	Problem	Language	Result	Execution time	Memory
545684		NemanjaSo2005	Roller Coaster Railroad (IOI16_railroad)	C++14	34 / 100	233 ms	14004 KiB

railroad

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll N,dp[20][66000],stepen[20];
struct grana{
   int gde;
   ll cena;
}pp;
vector<grana> graf[20];
long long plan_roller_coaster(std::vector<int> s, std::vector<int> u){
   N=s.size();
   for(int i=1;i<=5;i++){
      s.push_back(0);
      u.push_back(0);
   }
   for(int i=N;i>=1;i--){
      s[i]=s[i-1];
      u[i]=u[i-1];
   }
   stepen[1]=1;
   for(int i=2;i<=N+1;i++)
      stepen[i]=2*stepen[i-1];
   for(int i=1;i<=N;i++)
      for(int j=0;j<stepen[N+1];j++)
         dp[i][j]=1e18;
   for(int i=1;i<=N;i++)
      dp[i][0]=dp[i][stepen[i]]=0;
   for(int i=1;i<=N;i++)
      for(int j=i+1;j<=N;j++){
         pp.cena=max(u[j]-s[i],0);
         pp.gde=j;
         graf[i].push_back(pp);

         pp.cena=max(u[i]-s[j],0);
         pp.gde=i;
         graf[j].push_back(pp);
      }
   for(int pon=1;pon<=N;pon++){
      for(int i=1;i<=N;i++)
         for(int j=1;j<stepen[N+1];j++){
            if((j&stepen[i])==0)
               continue;
            for(int k=0;k<graf[i].size();k++)
               dp[i][j]=min(dp[i][j],dp[graf[i][k].gde][j-stepen[i]]+graf[i][k].cena);
         }
   }/*
   for(int i=1;i<=N;i++){
      cout<<i<<": ";
      for(int j=0;j<stepen[N+1];j++){
         if(dp[i][j]>=1e18)
            cout<<"inf ";
         else
            cout<<dp[i][j]<<" ";
      }
      cout<<endl;
   }*/
   ll res=1e18;
   for(int i=1;i<=N;i++)
      res=min(res,dp[i][stepen[N+1]-1]);
   return res;
}

Compilation message (stderr)

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:43:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<grana>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |             for(int k=0;k<graf[i].size();k++)
      |                         ~^~~~~~~~~~~~~~~

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