Submission #1214344

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214344		inesfi	Roller Coaster Railroad (IOI16_railroad)	C++20	34 / 100	120 ms	54708 KiB

railroad

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

#define ll long long

const ll HASHMAXI=(1<<17),POSEC=18,INFINI=(ll)1000*1000*1000*1000;
ll memo[HASHMAXI][POSEC];
ll nb,fin;
vector<ll> limites,arrivees;

vector<ll> trouve(ll v){
    vector<ll> a;
    a.clear();
    while (v>0){
        a.push_back(v%2);
        v/=2;
    }
    while ((ll)a.size()!=nb){
        a.push_back(0);
    }
    return a;
}

ll dp(ll hash,ll dernierpris){
    if (memo[hash][dernierpris]!=-1){
        return memo[hash][dernierpris];
    }
    if (hash==fin){
        memo[hash][dernierpris]=0;
        return 0;
    }
    vector<ll> r=trouve(hash);
    ll val=INFINI;
    for (int i=0;i<nb;i++){
        if (r[i]==0){
            val=min(val,dp(hash+(1<<i),i)+max((ll)0,arrivees[dernierpris]-limites[i]));
        }
    }
    /*if (val!=INFINI){
        cout<<hash<<" "<<dernierpris<<endl;
    }*/
    memo[hash][dernierpris]=val;
    return val;
}

ll plan_roller_coaster(vector<int> l,vector<int> a) {
    nb=(ll)l.size();
    fin=(1<<nb)-1;
    for (auto i:l){
        limites.push_back(i);
    }
    for (auto i:a){
        arrivees.push_back(i);
    }
    arrivees.push_back(-1);
    for (int i=0;i<HASHMAXI;i++){
        for (int j=0;j<POSEC;j++){
            memo[i][j]=-1;
        }
    }
    /*vector<ll> debug=trouve(6);
    for (auto i:debug){
        cout<<i<<" ";
    }
    cout<<endl;*/
    return dp(0,nb);
}

Compilation message (stderr)

railroad.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
railroad_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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