Submission #1314110

#	Time	Username	Problem	Language	Result	Execution time	Memory
1314110		activedeltorre	Roller Coaster Railroad (IOI16_railroad)	C++20	0 / 100	138 ms	16068 KiB

railroad

#include "railroad.h"
long long dp[70000][18];
using namespace std;
#include<vector>
#include<iostream>
#include<set>
long long vmax=1e12;
set<pair<long long,int> >st;
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    int n = (int) s.size();

    if(n<=1)
    {
        int maxmask=(1<<n)-1;
        for(int i=0;i<=maxmask;i++)
        {
            for(int j=0;j<n;j++)
            {
                dp[i][j]=vmax;
            }
        }
        for(int i=0;i<n;i++)
        {
            dp[(1<<i)][i]=0;
        }
        for(int i=1;i<maxmask;i++)
        {
            for(int last=0;last<n;last++)
            {
                if(((1<<last)&i)!=0)
                {
                    for(int j=0;j<n;j++)
                    {
                        if(((1<<j)&i)==0)
                        {
                            long long cost=max(0,t[last]-s[j]);
                            dp[i^(1<<j)][j]=min(dp[i^(1<<j)][j],dp[i][last]+cost);
                        }
                    }
                }
            }
        }
        long long best=vmax;
        for(int last=0;last<n;last++)
        {
            best=min(best,dp[maxmask][last]);
        }
        return best;
    }
    else
    {
        long long last=vmax;
        for(int i=0;i<n;i++)
        {
            st.insert({t[i],s[i]});
        }
        for(int i=1;i<=n;i++)
        {
            auto it=st.upper_bound({last+1,vmax});
            if(it==st.begin())
            {
                return 1;
            }
            it--;
            last=it->second;
            st.erase(it);
        }
        return 0;
    }
}

Compilation message (stderr)

railroad.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
railroad_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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