Submission #789876

#	Time	Username	Problem	Language	Result	Execution time	Memory
789876		pravcoder	Roller Coaster Railroad (IOI16_railroad)	C++14	34 / 100	308 ms	524288 KiB

railroad

#include "railroad.h"
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> v2ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;

ll plan_roller_coaster(vi s, vi t) {
    int n = (int) s.size();
    vll empty(n, 1e12);
    v2ll costs(n, empty);
    for (int i = 0; i < n-1; i++)
    {
        for (int j = i+1; j < n; j++)
        {
            costs[i][j] = (t[i] - s[j]) * (t[i] > s[j]);
            costs[j][i] = (t[j] - s[i]) * (t[j] > s[i]);
        }
    }
    v2ll d(1<<n, empty);
    for (int i = 0; i < n; i++)
    {
        d[1<<i][i] = 0;
    }
    ll ans = 1e12;
    for (int b = 1; b < (1<<n); b++)
    {
        for (int c = 0; c < n; c++)
        {
            if (b == (1 << n) - 1) {
                ans = min(ans, d[b][c]);
            }
            else {
                if ((b & (1 << c)) > 0) {
                    for (int i = 0; i < n; i++)
                    {
                        if ((b & (1 << i)) == 0) {
                            d[b | (1 << i)][i] = min(d[b | (1 << i)][i], d[b][c] + costs[c][i]);
                        }
                    }
                }
            }
        }
    }
    return ans;
}

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