Submission #415001

#	Time	Username	Problem	Language	Result	Execution time	Memory
415001		MeGustaElArroz23	Roller Coaster Railroad (IOI16_railroad)	C++14	0 / 100	2065 ms	337572 KiB

railroad

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

using namespace std;

typedef long long ll;
typedef vector<int> 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<16;i++){
        sol+=pot*x[i];
        pot*=2;
    }
}

int n;
vii in_out;
map<pair<vb,int>,int> sol; //le metemos uno mas

ll recurs(vb mask, int ac){
    //cerr << ac;
    mask[ac]=false;
    if (sol[pair<vb,int>{mask,ac}]) return sol[pair<vb,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[pair<vb,int>{mask,ac}]=mejor+1;
    return mejor;
}

//4 1 7 4 3 5 8 6 6

ll plan_roller_coaster(vi in, vi 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);
    for (int i=0;i<n;i++){ in_out[i]=pii{in[i],out[i]};}
    //cerr<<"HOLA";
    ll mejor=INF;
    for (int 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:31:1: warning: no return statement in function returning non-void [-Wreturn-type]
   31 | }
      | ^

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