Submission #281964

#	Time	Username	Problem	Language	Result	Execution time	Memory
281964		A02	Roller Coaster Railroad (IOI16_railroad)	C++14	34 / 100	106 ms	14088 KiB

railroad

#include "railroad.h"
#include <vector>
#include <iostream>
#include <set>
#include <algorithm>
#include <utility>

using namespace std;

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {

    int N = (int) s.size();

    vector<vector<long long> > bestDP ((1 << N) + 1, vector<long long> (N, ((long long) 1 << 62)));

    for (int i = 0; i < N; i++){
        bestDP[(1 << i)][i] = 0;
        //cout << s[i] << ' ' << t[i] << endl;
    }

    for (long long rails = 1; rails < (1 << N); rails++){

        for (long long last = 0; last < N; last++){
            if (rails & (1 << last)){
                for (int second_last = 0; second_last < N; second_last++){
                    bestDP[rails][last] = min(bestDP[rails][last], bestDP[rails ^ (1 << last)][second_last] + max(0, t[second_last] - s[last]));
                    //cout << ' ' << rails << ' ' << last << ' ' << second_last << ' ' << bestDP[rails ^ (1 << last)][second_last] << ' ' << t[second_last] << ' ' << s[last] << endl;
                }
            }
            //cout << bestDP[rails][last] << ' ' << rails << ' ' << last << endl;
        }
    }

    long long best = ((long long) 1 << 62);
    for (int i = 0; i < N; i++){
        best = min(best, bestDP[(1 << N) - 1][i]);
        //cout << bestDP[(1 << N) - 1][i] << endl;
    }


    return best;
}

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