Submission #1311801

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311801		settop	Roller Coaster Railroad (IOI16_railroad)	C++20	34 / 100	31 ms	11084 KiB

railroad

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

using namespace std;
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ll long long
#define fall(i,a,b) for(int i=a;i<=b;i++)
#define rfall(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
const ll inf=1e16;
typedef pair<ll,ll> pii;

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    int n = sz(s);

    vector<vector<ll>> dp((1<<n),vector<ll>(n)); //dp[mask][i]
    vector<vector<ll>> custo(n,vector<ll>(n));

    fall(i,0,n-1)
        fall(j,0,n-1) custo[i][j]=max(0,t[i]-s[j]);

    fall(i,0,(1<<n)-1)
        fall(j,0,n-1) dp[i][j]=inf;
    
    fall(i,0,n-1) dp[(1<<i)][i]=0;

    fall(mask,1,(1<<n)-1)
        fall(i,0,n-1){
            if(dp[mask][i]==inf) continue;
            fall(j,0,n-1){
                if((mask&(1<<j))) continue;
                int m=mask|(1<<j);
                dp[m][j]=min(dp[m][j],dp[mask][i]+custo[i][j]);
            }
        }
    
    ll ans=inf;

    fall(i,0,n-1) ans=min(ans,dp[(1<<n)-1][i]);

    return ans;
}

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