Submission #54076

#	Time	Username	Problem	Language	Result	Execution time	Memory
54076		Alexa2001	Roller Coaster Railroad (IOI16_railroad)	C++17	34 / 100	141 ms	9524 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll inf = 1e18;
const int Nmax = 17;
const int Nmaxx = 2e5 + 5;

int n, start[Nmaxx], finish[Nmaxx];
ll dp[1<<Nmax][Nmax];

int cnt[Nmaxx];
pair<int,int> a[Nmaxx];


ll solve1(vector<int> &start, vector<int> &finish)
{
    int i, j, k;

    for(i=0; i<(1<<n); ++i)
        for(j=0; j<n; ++j)
            dp[i][j] = inf;

    for(i=0; i<n; ++i) dp[1<<i][i] = 0;

    for(i=1; i<(1<<n); ++i)
        for(j=0; j<n; ++j)
            if(i&(1<<j))
                for(k=0; k<n; ++k)
                    if(!(i&(1<<k)))
                        dp[i^(1<<k)][k] = min(dp[i^(1<<k)][k], dp[i][j] + max(0, finish[j] - start[k]));

    ll ans = inf;
    for(j=0; j<n; ++j) ans = min(ans, dp[i-1][j]);
    return ans;
}

bool solve2()
{
    int i, j;

    for(i=1; i<=n; ++i) a[i] = {start[i], finish[i]}, cnt[i] = 0;
    sort(a+1, a+n+1);
    sort(finish+1, finish+n+1);

    j = 0;
    for(i=1; i<=n; ++i)
    {
        while(j+1<=n && finish[j+1] <= a[i].first) ++j;
        cnt[i] = j;
        cnt[i] -= (a[i].second <= a[i].first);
    }

    sort(cnt+1, cnt+n+1);
    for(i=1; i<=n; ++i)
        if(cnt[i] < i-1) return 0;
    return 1;
}

ll plan_roller_coaster(vector<int> s, vector<int> t)
{
    n = s.size();
    int i;
    for(i=1; i<=n; ++i) start[i] = s[i-1], finish[i] = t[i-1];

    if(n <= 16) return solve1(s, t);
    return solve2() ? 0 : 5;
}

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