Submission #394811

#	Time	Username	Problem	Language	Result	Execution time	Memory
394811		idk321	Roller Coaster Railroad (IOI16_railroad)	C++11	34 / 100	54 ms	11088 KiB

railroad

#include "railroad.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll M = 1000000000000000000LL;

int n;
vector<int> s;
vector<int> t;

ll solveFor(vector<int> a, vector<int> b)
{

}

bool  solveCur(int small, int big)
{
    bool cur = true;
    set<array<int, 2>> byS;
    for (int i = 0; i < n; i++)
    {
        if (i != small) byS.insert({s[i], i});
    }

    for (int i = 0; i < n; i++)
    {
        if (i != big && i != small)
        {
            auto it = byS.lower_bound({t[i], 0});
            if (it != byS.end() && (*it)[1] == i) it++;
            if (it == byS.end())
            {
                cur = false;
            } else byS.erase(it);
        }
    }

    for (int i = 0; i < n; i++)
    {
        if (i == small)
        {
            auto it = byS.lower_bound({t[i], 0});
            if (it != byS.end() && (*it)[1] == i) it++;
            if (it == byS.end())
            {
                cur = false;
            } else byS.erase(it);
        }
    }

    return cur;
}

long long plan_roller_coaster(std::vector<int> S, std::vector<int> T) {
    s = S;
    t = T;
    n = (int) s.size();


    if (n <= 16)
    {
        vector<vector<ll>> dp(1 << n, vector<ll>(n, M));

        for (int i = 1; i < (1 << n); i++)
        {

            int nbits = 0;
            int bit = -1;
            for (int j = 0; j < n; j++)
            {
                if ((i & (1 << j)))
                {
                     nbits++;
                     bit = j;
                }
            }

            if (nbits == 1)
            {
                dp[i][bit] = 0;
            } else
            {
                for (int j = 0; j < n; j++)
                {
                    if ((i & (1 << j)))
                    {
                        for (int k = 0; k < n; k++)
                        {
                            dp[i][j] = min(dp[i][j], dp[i ^ (1 << j)][k] + max(0, t[k] - s[j]));
                        }
                    }
                }
            }
        }

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




    return 0;
}

/*
3
5 3
1 2
3 1


*/

Compilation message (stderr)

railroad.cpp: In function 'll solveFor(std::vector<int>, std::vector<int>)':
railroad.cpp:16:1: warning: no return statement in function returning non-void [-Wreturn-type]
   16 | }
      | ^

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