Submission #1211865

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211865		Marco_Escandon	Roller Coaster Railroad (IOI16_railroad)	C++20	34 / 100	61 ms	21960 KiB

railroad

#include "railroad.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    int n = (int) s.size();
    vector<vector<ll>> dp(1<<n+1,vector<ll>(n+1,1e17));
    ll ans=1e17;
    for(int i=1; i<(1<<n); i++)
    {
        for(int j=0; j<n; j++)
        {
            if((i&(1<<j))==0) continue;
            if(__builtin_popcount(i)==1) dp[i][j]=0;
            for(int k=0; k<n; k++)
            {
                if((i&(1<<k))==0||k==j) continue;
                dp[i][j]=min(dp[i][j],dp[i^(1<<j)][k]+(ll)max(t[k]-s[j],0));
            }
            if(__builtin_popcount(i)==n) ans=min(ans,dp[i][j]);
        }
    }
    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