Submission #415009

#	Time	Username	Problem	Language	Result	Execution time	Memory
415009		MeGustaElArroz23	Roller Coaster Railroad (IOI16_railroad)	C++14	34 / 100	1505 ms	13100 KiB

railroad

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

using namespace std;

typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> pii;
typedef vector<pii> vii;
typedef vector<vii> vvii;
typedef vector<bool> vb;

const ll INF=1000000000000000000;

ll potencia(ll a, ll n){
    if (n==0) return 1;
    ll sol=potencia(a,n/2);
    sol*=sol;
    if (n%2) sol*=a;
    return sol;
}

ll vb_to_int(vb x){
    ll pot=1;
    ll sol=0;
    for (int i=0;i<x.size();i++){
        sol+=pot*x[i];
        pot*=2;
    }
    return sol;
}

int n;
vii in_out;
vvi sol; //le metemos uno mas

ll recurs(vb mask, int ac){
    //cerr << ac;
    mask[ac]=false;
    if (sol[vb_to_int(mask)][ac]) return sol[vb_to_int(mask)][ac]-1;
    for (int i=0;i<n;i++){
        if (mask[i]) break;
        if (i==n-1) return 0;
    }
    ll mejor=INF;
    for (int i=0;i<n;i++){
        if (mask[i]) mejor=min(mejor,recurs(mask, i)+max(ll(0),in_out[ac].second-in_out[i].first));
    }
    sol[vb_to_int(mask)][ac]=mejor+1;
    return mejor;
}

//4 1 7 4 3 5 8 6 6

ll plan_roller_coaster(vector<int> in, vector<int> out) {
    //if (false){ //subtask 3
    //    int n=in.size();
    //    multiset<pii> pares;
    //    for (int i=0;i<n;i++) pares.insert(pii{in[i],out[i]});
    //    int ac=1;
    //    for (int i=0;i<n;i++){
    //        //cerr << ac << ' ';
    //        cerr << ac << ' ';
    //        auto x=pares.upper_bound(pii{ac,0});
    //        pii y=*x;
    //        if (x==pares.end()) return 1;
    //        if (i<n-1 and pares.upper_bound(pii{y.second,0})==pares.end()) x++;
    //        if (x==pares.end()) return 1;
    //        ac=(*x).second;
    //        pares.erase(x);
    //    }
    //    return 0;
    //}
    n=in.size();
    //cerr<<"HOLA";
    in_out=vii(n);
    sol=vvi(potencia(2,n),vi(n,0));
    for (ll i=0;i<n;i++){ in_out[i]=pii{in[i],out[i]};}
    //cerr<<"HOLA";
    ll mejor=INF;
    for (ll i=0;i<n;i++) mejor=min(mejor,recurs(vb(n,true),i));
    return mejor;
}

Compilation message (stderr)

railroad.cpp: In function 'll vb_to_int(vb)':
railroad.cpp:27:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for (int i=0;i<x.size();i++){
      |                  ~^~~~~~~~~

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