Submission #1022135

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022135		parsadox2	Roller Coaster Railroad (IOI16_railroad)	C++17	34 / 100	32 ms	10872 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 17;
long long inf = 1e18 + 10;
int n;
long long dp[(1 << N)][N];

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    n = s.size();
    if(n >= 17)
        return 0;
    long long ans = inf;
    for(int mask = 1 ; mask < (1 << n) ; mask++)  for(int i = 0 ; i < n ; i++)
    {
        dp[mask][i] = inf;
        if(!((mask >> i) & 1))
            continue;
        if(__builtin_popcount(mask) == 1)
        {
            dp[mask][i] = 0;
            continue;
        }
        for(int j = 0 ; j < n ; j++)  if(j != i && ((mask >> j) & 1))
            dp[mask][i] = min(dp[mask][i] , dp[mask - (1 << i)][j] + max(0 , t[j] - s[i]));
    }
    for(int i = 0 ; i < n ; i++)
        ans = min(ans , dp[(1 << n) - 1][i]);
    return ans;
}
/*
4
1 7
4 3
5 8
6 6
*/

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