Submission #617200

#	Time	Username	Problem	Language	Result	Execution time	Memory
617200		Drew_	Roller Coaster Railroad (IOI16_railroad)	C++17	34 / 100	83 ms	10896 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define f1 first
#define s2 second
#define size(x) (int)x.size()

using ll = long long;
using ii = pair<int, int>;

const ll inf = 1e18 + 69;


namespace sub1
{
    ll solve(vector<int> s,vector<int> t)
    {
        int n = size(s);
        vector<ii> v(n);
        for (int i = 0; i < n; ++i)
            v[i] = {s[i], t[i]};
        sort(v.begin(), v.end());

        ll mn = inf;
        do
        {
            ll ctr = 0;
            for (int i = 0, cur = 1; i < n; ++i)
            {
                ctr += max(0, cur - v[i].f1);
                cur = v[i].s2;
            }
            mn = min(mn, ctr);
        } while (next_permutation(v.begin(), v.end()));
        return mn;
    }
}

namespace sub2
{
    ll solve(vector<int> s, vector<int> t)
    {
        int N = size(s);
        vector<vector<ll>> dp(N, vector<ll>(1 << N, inf));
        const auto rc = [&](const auto &self, int id, int mask) -> ll
        {
            if (mask == (1 << N) - 1)
                return 0;
            if (dp[id][mask] != inf)
                return dp[id][mask];
            for (int i = 0; i < N; ++i) if (~mask >> i & 1)
                dp[id][mask] = min(dp[id][mask], max(0, t[id] - s[i]) + self(self, i, mask | (1 << i)));
            return dp[id][mask];
        };

        ll res = inf;
        for (int i = 0; i < N; ++i)
            res = min(res, rc(rc, i, 1 << i));
        return res;
    }
}  

namespace sub3
{
    ll solve(vector<int> s, vector<int> t)
    {
        int n = size(s);

        set<ii> st;
        for (int i = 0; i < n; ++i)
            st.insert({t[i], s[i]});

        for (int prv = 1e9; !st.empty();)
        {
            auto it = st.upper_bound(mp(prv, 1e9));
            if (it == st.begin())
                return 1;
            it = prev(it);
            prv = (it -> s2);
            st.erase(it);

            cerr << "> " << prv << '\n';
        }
        return 0;          
    }
}

ll plan_roller_coaster(vector<int> s, vector<int> t) {
    // cerr << "sub1 " << sub1 :: solve(s, t) << '\n';
    // cerr << "sub3 " << sub3 :: solve(s, t) << '\n';
    return sub2 :: solve(s, t);
}

// int main() {
//     mt19937 RNG(69);
//     const auto randint = [&](int l, int r) -> int
//     {
//         return uniform_int_distribution<int>(l, r)(RNG);
//     };

//     for (int rep = 0; rep < 100; ++rep)
//     {
//         cerr << "rep " << rep << '\n';

//         int n = 5;
//         vector<int> s(n), t(n);
//         for (int i = 0; i < n; ++i)
//             s[i] = randint(1, 10), t[i] = randint(1, 10);

//         if (!!sub1::solve(s, t) != !!sub3::solve(s, t))
//         {
//             cout << n << '\n';
//             for (int i = 0; i < n; ++i)
//                 cout << s[i] << " " << t[i] << '\n';
//             return 0;
//         }
//     }
//     return 0;
// }

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