제출 #1025058

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1025058		slivajan	Roller Coaster Railroad (IOI16_railroad)	C++17	11 / 100	2095 ms	6852 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long un;
typedef vector<un> vuc;


#define REP(i, a, b) for(un i = (un)a; i < (un)b; i++)
#define FEAC(i, a) for (auto&& i : a)
#define vec vector
#define ALL(x) (x).begin(), (x).end()

constexpr un INF = INT64_MAX;

un compute(vec<int> s, vec<int> t, vuc perm){

    un ret = 0;

    REP(i, 0, perm.size()-1){
        ret += max(0, t[perm[i]] - s[perm[i+1]]);
    }

    return ret;
}

un easy(std::vector<int> s, std::vector<int> t, un N){

    vuc perm(N);
    iota(ALL(perm), 0);


    un ret = INF;

    do{
        ret = min(ret, compute(s, t, perm));
    } while(next_permutation(ALL(perm)));

    return ret;
}

vuc compute_ends(std::vector<int> s, std::vector<int> t, vuc toUse, un N){

    vuc tab(N, -1);
    REP(i, 0, toUse.size()){
        tab[toUse[i]] = i;
    }
    sort(ALL(toUse));

    vuc ret(toUse.size(), INF);

    do{
        ret[tab[toUse[toUse.size()-1]]] = min(ret[tab[toUse[toUse.size()-1]]], compute(s, t, toUse));
    } while(next_permutation(ALL(toUse)));

    return ret;
}

vuc compute_starts(std::vector<int> s, std::vector<int> t, vuc toUse, un N){

    vuc tab(N, -1);
    REP(i, 0, toUse.size()){
        tab[toUse[i]] = i;
    }
    sort(ALL(toUse));

    vuc ret(toUse.size(), INF);

    do{
        ret[tab[toUse[0]]] = min(ret[tab[toUse[0]]], compute(s, t, toUse));
    } while(next_permutation(ALL(toUse)));

    return ret;
}

un meet_in_mid(std::vector<int> s, std::vector<int> t, un N){

    un ret = INF;

    REP(i, 0, 1<<N){
        if (__popcount(i) != (N/2)) continue;

        vuc A, B;

        REP(j, 0, N){
            if (i & (1 << j)) A.push_back(j);
            else B.push_back(j);
        }

        vuc A_ret = compute_ends(s, t, A, N);
        vuc B_ret = compute_starts(s, t, B, N);

        REP(x, 0, A.size()) REP(y, 0, B.size()) {
            ret = min(ret, A_ret[x] + B_ret[y] + max(0, t[A[x]] - s[B[y]]));
        }
    }

    return ret;
}

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    un N = (un) s.size();
    

    // if (N <= 8) return easy(s, t, N);
    if (N <= 16) return meet_in_mid(s, t, N);

    return 0;
}

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