Submission #1191751

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191751		simona1230	Roller Coaster Railroad (IOI16_railroad)	C++20	0 / 100	25 ms	4676 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;

long long dp[100001][16];
int s[100001],f[100001];
int n;
long long plan_roller_coaster(vector<int> v1, vector<int> v2)
{
    n=v1.size();
    for(int i=0;i<(1<<n);i++)
        for(int j=0;j<n;j++)dp[i][j]=-1;
    for(int i=0;i<v1.size();i++)
        s[i]=v1[i],f[i]=v2[i];
        long long ans=1e18;
    for(int i=0;i<(1<<n);i++)
    {
        for(int j=0;j<n;j++)
        {
            if(!((1<<j)&i))continue;
            if(i-(1<<j)==0)
            {
                if(s[j]==1)
                {
                    //cout<<"+ "<<j<<endl;
                    dp[i][j]=0;
                }
                if(i==(1<<n)-1&&dp[i][j]!=-1)
                    ans=min(ans,dp[i][j]);
                continue;
            }
            for(int x=0;x<n;x++)
            {
                if(x==j||!(i&(1<<x)))continue;
                if(dp[i-(1<<j)][x]!=-1)
                {
                    if(dp[i][j]==-1)dp[i][j]=dp[i-(1<<j)][x]+max(0,f[x]-s[j]);
                    else dp[i][j]=min(dp[i][j],dp[i-(1<<j)][x]+max(0,f[x]-s[j]));
                }
            }
            if(i==(1<<n)-1&&dp[i][j]!=-1)
                ans=min(ans,dp[i][j]);
                //cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
        }
    }


    return ans;
}

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