Submission #221153

#	Time	Username	Problem	Language	Result	Execution time	Memory
221153		joseacaz	Roller Coaster Railroad (IOI16_railroad)	C++17	34 / 100	73 ms	8576 KiB

railroad

#include "railroad.h"
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;

const int MAXN = 16;
const ll INF = (1LL << 62LL);
ll DP[(1 << MAXN)][MAXN];

ll plan_roller_coaster(vi s, vi t)
{
    int N = s.size();
    if(N > 16)
        return 0;

    for(int m = (1 << N) - 1; m >= 0; m--)
    {
        for(int i = 0; i < N; i++)
        {
            if(m == (1 << N) - 1)
            {
                DP[m][i] = 0;
                continue;
            }
            DP[m][i] = INF;
            if(!(m & (1 << i)))
                continue;
            for(int j = 0; j < N; j++)
            {
                if(m & (1 << j))
                    continue;
                DP[m][i] = min(DP[m][i], DP[m | (1 << j)][j] + max(t[i] - s[j], 0));
            }
        }
    }
    ll ans = INF;
    for(int i = 0; i < N; i++)
        ans = min(ans, DP[(1 << i)][i]);
    return ans;
}

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