Submission #366751

#	Time	Username	Problem	Language	Result	Execution time	Memory
366751		BartolM	Roller Coaster Railroad (IOI16_railroad)	C++17	34 / 100	124 ms	31468 KiB

railroad

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

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const ll MAX=(ll)INF*INF;
const int N=2e5+5;

int n;
pii p[N];
ll dp[(1<<16)+5][17];

ll rek(int mask, int pr) {
    int siz=__builtin_popcount(mask);
    if (siz==n) return 0;

    ll &ret=dp[mask][pr];
    if (ret!=-1) return ret;
    ret=MAX;

    for (int i=0; i<n; ++i) {
        if (mask & (1<<i)) continue;
        ret=min(ret, rek(mask | (1<<i), i)+max(p[pr].Y-p[i].X, 0));
    }
    return ret;
}

long long plan_roller_coaster(vector<int> s, vector<int> t) {
    n=s.size();
    for (int i=0; i<n; ++i) p[i]=mp(s[i], t[i]);
    p[n]=mp(0, 1);

    memset(dp, -1, sizeof dp);
    ll sol=rek(0, n);

    return sol;
}

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