Submission #1264444

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264444		silentloop	Roller Coaster Railroad (IOI16_railroad)	C++20	34 / 100	38 ms	9032 KiB

railroad

#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
using namespace std;
ll INF=16e9+1;
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    ll n=sz(s), i, mask, j, k, ans;
    vector<vector<ll>>dp(n,vector<ll>((1<<n),INF));
    for(i=0; i<n; i++)
        dp[i][0]=0;
    for(i=0; i<(1<<n); i++)
    {
        for(j=0; j<n; j++)
        {
            if(((1<<j)&i))
                continue;
            for(k=0; k<n; k++)
            {
                if(k==j||((1<<k)&i)==0)
                    continue;
                ll ant=(i^(1<<k));
                //cout << dp[j][i] << ' ' << dp[k][ant] << ' ' << t[j]-s[k] << '\n';
                dp[j][i]=min(dp[j][i],dp[k][ant]+max(0,t[j]-s[k]));
                //cout << dp[j][i] << '\n';
            }
        }
    }
    ans=INF;
    mask=(1<<n)-1;
    for(i=0; i<n; i++)
    {
        ans=min(ans,dp[i][mask^(1<<i)]);
    }
    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: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 0 / 30
• Subtask 4: 0 / 36