Submission #99982

#	Time	Username	Problem	Language	Result	Execution time	Memory
99982		shenxy	Roller Coaster Railroad (IOI16_railroad)	C++11	0 / 100	109 ms	17792 KiB

railroad

#include "railroad.h"
#include <vector>
#include <algorithm>
#include <utility>
#include <cstring>
#define INF 1000000000000000000LL
using namespace std;
int n;
vector< pair<int, int> > speeddat;
long long int dptable[17][1 << 16];
int LSOne(int i) {
    return i & (-i);
}
int logtwo(int i) {
    int ans = 0;
    while (i) {
        ans += 1;
        i >>= 1;
    }
    return ans;
}
long long int speeddp(int sp, int mask) {
    if (mask == 0) return 0;
    if (dptable[sp][mask] != -1) return dptable[sp][mask];
    long long int ans = INF;
    int temp = mask;
    while (temp) {
        int X = LSOne(temp);
        if (sp == 0) {
            ans = min(ans, speeddp(speeddat[logtwo(X)].first, mask & (~X)));
        } else {
            ans = min(ans, speeddp(speeddat[logtwo(X)].first, mask & (~X)) + max(0, speeddat[sp].first - speeddat[logtwo(X)].first));
        }
        temp = temp & (~X);
    }
    return dptable[sp][mask] = ans;
}
long long int plan_roller_coaster(vector<int> s, vector<int> t) {
    n = s.size();
    for (int i = 0; i < n; i++) {
        speeddat.push_back(make_pair(t[i], s[i]));
    }
    sort(speeddat.begin(), speeddat.end());
    if (n > 16) {
        return 0;
    } else {
        memset(dptable, -1, sizeof(dptable));
        return speeddp(0, (1 << n) - 1);
    }
}

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