Submission #394734

#	Time	Username	Problem	Language	Result	Execution time	Memory
394734		kshitij_sodani	Roller Coaster Railroad (IOI16_railroad)	C++14	34 / 100	61 ms	10564 KiB

railroad

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'


#include "railroad.h"
llo dp[1<<17][17];
long long plan_roller_coaster(vector<int> ss,vector<int> tt) {
    int n = (int) ss.size();
  /*  for(auto j:ss){
    	cout<<j<<",";
    }
    cout<<endl;
    for(auto j:tt){
    	cout<<j<<",";
    }
    cout<<endl;*/
    for(int i=1;i<(1<<n);i++){
    	for(int j=0;j<n;j++){
    		dp[i][j]=(llo)1e18;
    		if((1<<j)&i){
    			if(i-(1<<j)==0){
    				dp[i][j]=0;
    				continue;
    			}
    			for(int k=0;k<n;k++){
    				if(k!=j){
    					if((1<<k)&i){
    						/*if(i==1+8 and j==3){
    							cout<<k<<","<<tt[k]<<":"<<ss[j]<<endl;
    						}*/
    						dp[i][j]=min(dp[i][j],dp[i-(1<<j)][k]+max(tt[k]-ss[j],0));
    					}
    				}
    			}
    		}
    	}
    }


    llo ans=1e18;
  //  cout<<dp[1+(1<<3)][3]<<endl;
    for(int i=0;i<n;i++){
    	ans=min(ans,dp[(1<<n)-1][i]);
    //	cout<<dp[(1<<n)-1][i]<<":";
    }
   // cout<<endl;













    
    return ans;
}

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