Submission #286334

#	Time	Username	Problem	Language	Result	Execution time	Memory
286334		SamAnd	Roller Coaster Railroad (IOI16_railroad)	C++17	34 / 100	111 ms	11648 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
typedef long long ll;
const int N = 22;
const ll INF = 1000000009000000009;
struct ban
{
    int s, t;
};

int n;
ban a[N];

bool operator<(const ban& a, const ban& b)
{
    if (a.s < b.s)
        return true;
    if (a.s > b.s)
        return false;
    return a.t < b.t;
}

ban b[N];

ll dp[(1 << N)][N];

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t)
{
    n = sz(s);
    //srand(time(0));
    for (int i = 1; i <= n; ++i)
    {
        a[i].s = s[i - 1];
        a[i].t = t[i - 1];
        //a[i].s = rand() % 30 + 1;
        //a[i].t = rand() % 30 + 1;
    }

    for (int x = 1; x < (1 << n); ++x)
    {
        for (int i = 0; i < n; ++i)
        {
            dp[x][i] = INF;
            if (!(x & (1 << i)))
                continue;
            int y = (x ^ (1 << i));
            if (!y)
                dp[x][i] = 0;
            for (int j = 0; j < n; ++j)
            {
                if (!(y & (1 << j)))
                    continue;
                dp[x][i] = min(dp[x][i], dp[y][j] + max(0, t[j] - s[i]));
            }
        }
    }

    ll yans = INF;
    for (int i = 0; i < n; ++i)
        yans = min(yans, dp[(1 << n) - 1][i]);
    return yans;

    /*sort(a + 1, a + n + 1);
    ll ans = 0;
    for (int i = 1; i < n; ++i)
    {
        ans += max(0, a[i].t - a[i + 1].s);
    }
    for (int i = 1; i <= n; ++i)
        b[i] = a[i];
    do
    {
        ll yans = 0;
        for (int i = 1; i < n; ++i)
        {
            yans += max(0, a[i].t - a[i + 1].s);
        }
        if (yans < ans)
        {
            ans = yans;
            for (int i = 1; i <= n; ++i)
                b[i] = a[i];
        }
    } while (next_permutation(a + 1, a + n + 1));
    for (int i = 1; i <= n; ++i)
        printf("%d %d\n", b[i].s, b[i].t);
    return ans;*/
}

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